가능한 인터뷰 질문 : 모든 겹치는 간격을 찾는 방법

가능한 인터뷰 질문 : 모든 겹치는 간격을 찾는 방법

---

내 프로젝트에서이 문제를 접했기 때문에 인터뷰 질문 자체 는 아니지만 괜찮은 중재 질문이 될 수 있다고 생각했습니다.

N 쌍의 간격, 예를 들어 정수가 있습니다. O (N) 시간에 서로 겹치는 모든 간격을 식별해야합니다. 예를 들어,

{1, 3} {12, 14} {2, 4} {13, 15} {5, 10}

대답은 {1, 3}, {12, 14}, {2, 4}, {13, 15}입니다. 그룹화 할 필요가 없으므로 결과는 예제와 같이 임의의 순서로 표시 될 수 있습니다.

KMP 알고리즘이 문자열 검색에 O (N)을 사용하기 때문에 방금 O (N) 시간을 던졌습니다. :디

제가 생각 해낸 최고의 것은 프로젝트에서 지금 사용하고있는 것은 O (N ^ 2)입니다. 예, 무차별 대입은 꽤 슬프지만 아무도 불평하지 않으므로 리팩토링하지 않을 것입니다. : P 그래도 더 큰 마음이 더 우아한 해결책이 있는지 궁금했다.

---

간격의 끝점을 배열에 던져 시작점 또는 끝점으로 표시합니다. 간격이 닫힌 경우 시작점 앞에 끝점을 배치하고 반쯤 열린 경우 반대 방향으로 연결을 끊는 방식으로 정렬합니다.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E

그런 다음 목록을 반복하여 우리가있는 간격 수를 추적합니다 (이는 처리 된 시작 지점 수에서 끝 지점 수를 뺀 수와 같습니다). 이미 간격에있는 동안 시작 지점에 도달 할 때마다 이는 중첩 간격이 있어야 함을 의미합니다.

1S, 2S, 3E, 4E, 5S, 10E, 12S, 13S, 14E, 15E
    ^                          ^
   overlap                    overlap

끝점과 함께 데이터를 저장하고 어떤 간격에 있는지 추적하여 어떤 간격과 겹치는 지 찾을 수 있습니다.

이것은 정렬이 주요 요소 인 O (N logN) 솔루션입니다.

---

시작 지점별로 간격을 정렬합니다. 그런 다음이 목록을 접어 각 간격을 이웃 (예 : (1,4), (2,6)-> (1,6))과 병합합니다. 결과 목록에는 겹치는 파트너가없는 간격이 포함됩니다. 원래 목록에서 필터링하십시오.

이것은 (n log n) 알고리즘으로 수행 할 수있는 초기 정렬 작업 이후 시간에 선형 적입니다. 그 문제를 어떻게 해결할 수 있을지 모르겠습니다. 첫 번째 작업의 입력 및 출력의 이미 정렬 된 순서를 활용하면 끝에있는 '중복 필터링'작업조차도 선형입니다.

다음은 Haskell의 구현입니다.

-- Given a list of intervals, select those which overlap with at least one other inteval in the set.
import Data.List

type Interval = (Integer, Integer)

overlap (a1,b1)(a2,b2) | b1 < a2 = False
                       | b2 < a1 = False
                       | otherwise = True

mergeIntervals (a1,b1)(a2,b2) = (min a1 a2, max b1 b2)

sortIntervals::[Interval]->[Interval]
sortIntervals = sortBy (\(a1,b1)(a2,b2)->(compare a1 a2))

sortedDifference::[Interval]->[Interval]->[Interval]
sortedDifference [] _ = []
sortedDifference x [] = x
sortedDifference (x:xs)(y:ys) | x == y = sortedDifference xs ys
                              | x < y  = x:(sortedDifference xs (y:ys))
                              | y < x  = sortedDifference (x:xs) ys

groupIntervals::[Interval]->[Interval]
groupIntervals = foldr couldCombine []
  where couldCombine next [] = [next]
        couldCombine next (x:xs) | overlap next x = (mergeIntervals x next):xs
                                 | otherwise = next:x:xs

findOverlapped::[Interval]->[Interval]
findOverlapped intervals = sortedDifference sorted (groupIntervals sorted)
  where sorted = sortIntervals intervals

sample = [(1,3),(12,14),(2,4),(13,15),(5,10)]

---

Intervales-on-the-line 문제에 대한 표준 접근 방식은 시작점에 따라 문제를 정렬 한 다음 처음부터 끝까지 걸어가는 것입니다. O(n*logn)( O(n)이미 정렬 된 경우)

end = 0;
for (current in intervals) {
    if current.start < end {
        // there's an intersection!
        // 'current' intersects with some interval before it
        ...
    }
    end = max(end, current.end)
}

---

O (N)에 대해서는 확실하지 않지만 먼저 각 튜플의 첫 번째 숫자로 정렬 한 다음 튜플의 첫 번째 숫자가 이전 튜플에서 본 가장 큰 숫자보다 큰 숫자를 순차적으로 찾으면 어떻게 될까요? 다음 튜플과 겹치지 않습니다.

따라서 먼저 다음을 얻을 수 있습니다.

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

4 (최대) <5 및 10 <12이므로 {5, 10}이 분리됩니다.

이것은 우리가 만나는 가장 큰 숫자를 추적하는 것을 수반하고, 시작 숫자가 더 큰 튜플을 찾을 때마다 다음 숫자와 겹치는 지 확인합니다.

이것은 정렬 알고리즘의 효율성에 따라 달라집니다. 후자의 프로세스는 O (N)이기 때문입니다.

---

시작점과 끝점 사이의 차이가 작다고 가정합니다 (예 : 32 미만). 1..32. 그런 다음 각 간격을 32 비트 워드의 비트 패턴으로 쓸 수 있습니다. 예 : [1, 2] -> 001; [2, 3]-> 010; [1, 3] -> 011; [2, 3, 4] -> 110. 비트 단위 AND가 0이 아닌 경우 두 간격 또는 간격 조합이 겹칩니다 . 예. , 0이 아니기 때문에 [1,2]겹칩니다 . O (n) alg는 지금까지 본 간격과 각각의 새로운 간격의 실행중인 비트 단위 OR을 유지하는 것입니다.[1,3]001&011 == 001AND

bitsSoFar = 0
for (n=0; n < bitPatterns.length; n++)
    if (bitPatterns[n] & bitsSoFar != 0)
        // overlap of bitPatterns[n] with an earlier pattern
        bitsSoFar |= bitPatterns[n]

운동으로 남음 :

• 알고리즘을 수정하여 나중에 비트 패턴과 겹치는 부분도 식별합니다.

• O (1)의 간격에 대한 비트 패턴을 계산합니다.

---

N 쌍의 간격이 정수이면 O (n)에서 얻을 수 있습니다.

쌍의 첫 번째 숫자로 정렬 한 다음 두 번째 숫자로 정렬합니다. 모두 정수이면 버킷 정렬 또는 기수 정렬을 사용하여 O (n)으로 가져올 수 있습니다.

{1, 3}, {2,4}, {5, 10}, {12, 14}, {13, 15}

그런 다음 하나씩 결합하십시오.

{1,3}

겹치는 {1,3} 및 {2,4}가있는 {1,4}

{1,4}, {5,10}

{1,4}, {5,10}, {12,14}

{1,4}, {5,10}, {12,15} (겹침 {12,14} 및 {13,15} 포함)

조합은 O (N) 시간이 걸립니다.

---

이 문제는 요소 고유성 문제로 줄일 수 있습니다.

요소 고유성은 Omega (n log n) 하한 (비교 횟수 계산)이 있으므로 그보다 더 잘할 수는 없습니다.

---

다음 O(N lg N)은 @Nikita Rybak에서 제공하는 답변을 확장하는 Java 구현입니다.

내 솔루션은 적어도 하나의 다른 간격과 겹치는 모든 간격을 찾아서 둘 다 겹치는 간격으로 계산합니다. 예를 들어 두 개의 간격 (1, 3)과 (2, 4)OP의 원래 질문에서 서로 겹치므로이 경우에는 두 개의 겹치는 간격이 있습니다. 즉, 구간 A가 구간 B와 겹치는 경우 겹치는 결과 구간 집합에 A와 B를 모두 추가합니다.

이제 간격을 고려 (1, 100), (10, 20)하고 (30, 50). 내 코드는 다음을 찾습니다.

[ 10,  20] overlaps with [  1, 100]
[ 30,  50] overlaps with [  1, 100]

Resulting intervals that overlap with at least one other interval:
[  1, 100]
[ 30,  50]
[ 10,  20]

(1, 100)두 번 계산되는 것을 방지하기 위해 Set고유 한 Interval 객체 만 유지 하는 Java 를 사용 합니다.

내 솔루션은이 개요를 따릅니다.

1. 시작 지점을 기준으로 모든 간격을 정렬합니다. 이 단계는 O(N lg N)입니다.
2. intervalWithLatestEnd최신 끝점과의 간격을 추적 합니다.
3. 정렬 된 목록의 모든 간격을 반복합니다. 간격이와 겹치면 intervalWithLatestEnd둘 다 세트에 추가하십시오. intervalWithLatestEnd필요할 때 업데이트하십시오 . 이 단계는 O(N)입니다.
4. 세트를 반환하고 필요한 경우 목록으로 변환합니다.

총 실행 시간은 O(N lg N)입니다. 크기의 출력 세트가 필요합니다 O(N).

이행

집합에 간격을 추가하기 위해 equals()예상대로 를 재정의하는 사용자 지정 Interval 클래스를 만들었습니다 .

class Interval {
    int start;
    int end;
    Interval(int s, int e) { 
        start = s; end = e; 
    }

    @Override
    public String toString() {
        return String.format("[%3d, %3d]", start, end);
    }
    @Override
    public int hashCode() {
        final int prime = 31;
        int result = 1;
        result = prime * result + start;
        result = prime * result + end;
        return result;
    }
    @Override
    public boolean equals(Object obj) {
        if (this == obj)
            return true;
        if (obj == null)
            return false;
        if (getClass() != obj.getClass())
            return false;
        final Interval other = (Interval) obj;
        if (start != other.start)
            return false;
        if (end != other.end)
            return false;
        return true;
    }
}

다음은 알고리즘을 실행하는 코드입니다.

private static List<Interval> findIntervalsThatOverlap(List<Interval> intervals) {

    // Keeps unique intervals.
    Set<Interval> set = new HashSet<Interval>();

    // Sort the intervals by starting time.
    Collections.sort(intervals, (x, y) -> Integer.compare(x.start, y.start));

    // Keep track of the interval that has the latest end time.
    Interval intervalWithLatestEnd = null;

    for (Interval interval : intervals) {

        if (intervalWithLatestEnd != null &&
            interval.start < intervalWithLatestEnd.end) {

            // Overlap occurred.
            // Add the current interval and the interval it overlapped with.
            set.add(interval); 
            set.add(intervalWithLatestEnd);

            System.out.println(interval + " overlaps with " +
                               intervalWithLatestEnd);
        }

        // Update the interval with latest end.
        if (intervalWithLatestEnd == null ||
            intervalWithLatestEnd.end < interval.end) {

            intervalWithLatestEnd = interval;
        }
    }
    // Convert the Set to a List.
    return new ArrayList<Interval>(set);
}

테스트 케이스

다음은 OP의 원래 간격을 실행하는 테스트 케이스입니다.

public static void testcase() {

    List<Interval> intervals = null;
    List<Interval> result = null;

    intervals = new ArrayList<Interval>();

    intervals.add(new Interval(1, 3));
    intervals.add(new Interval(12, 14));
    intervals.add(new Interval(2, 4));
    intervals.add(new Interval(13, 15));
    intervals.add(new Interval(5, 10));


    result = findIntervalsThatOverlap(intervals);
    System.out.println("Intervals that overlap with at least one other interval:");
    for (Interval interval : result) {
        System.out.println(interval);
    }
}

결과 :

[  2,   4] overlaps with [  1,   3]
[ 13,  15] overlaps with [ 12,  14]
Intervals that overlap with at least one other interval:
[  2,   4]
[  1,   3]
[ 13,  15]
[ 12,  14]

마지막으로 고급 테스트 사례가 있습니다.

public static void testcase() {

    List<Interval> intervals = null;
    List<Interval> result = null;

    intervals = new ArrayList<Interval>();

    intervals.add(new Interval(1, 4));
    intervals.add(new Interval(2, 3));
    intervals.add(new Interval(5, 7));
    intervals.add(new Interval(10, 20));
    intervals.add(new Interval(15, 22));
    intervals.add(new Interval(9, 11));
    intervals.add(new Interval(8, 25));
    intervals.add(new Interval(50, 100));
    intervals.add(new Interval(60, 70));
    intervals.add(new Interval(80, 90));


    result = findIntervalsThatOverlap(intervals);
    System.out.println("Intervals that overlap with at least one other interval:");
    for (Interval interval : result) {
        System.out.println(interval);
    }
}

결과 :

[  2,   3] overlaps with [  1,   4]
[  9,  11] overlaps with [  8,  25]
[ 10,  20] overlaps with [  8,  25]
[ 15,  22] overlaps with [  8,  25]
[ 60,  70] overlaps with [ 50, 100]
[ 80,  90] overlaps with [ 50, 100]
Intervals that overlap with at least one other interval:
[  2,   3]
[  8,  25]
[  9,  11]
[ 50, 100]
[  1,   4]
[ 15,  22]
[ 10,  20]
[ 60,  70]
[ 80,  90]

---

It's been quite a while since I've used it, but the solution I used was an derivative of the red-black tree described in Introduction to Algorithms called an interval tree. It is a tree sorted by interval start, so you can quickly (binary search) first the first eligible node. IIRC, the nodes were ordered by a property that let's you stop "walking" the tree when the candidates nodes can't match your interval. So I think it was O(m) search, where m is the number of matching intervals.

I search found this implementation.

Brett

[edit] Rereading the question, this isn't what you asked. I think this is the best implementation when you have a list of (for instance) meetings already scheduled in conference rooms (which are added to the tree) and you want to find which rooms are still available for a meeting with a new start and duration (the search term). Hopefully this solution has some relevance, though.

---

This is a simple O(N*log(N)) implementation in Python:

def overlapping(intervals):
    last = (-1, -1)
    overlapping = set()

    for curr in sorted(intervals, key=lambda p: p[0]):
        if curr[0] < last[1]:
            overlapping.add(curr)
            overlapping.add(last)
        last = max(curr, last, key=lambda p: p[1])

    return list(overlapping - set((-1, -1)))

print overlapping([(1, 3), (12, 14), (2, 4), (13, 15), (5, 10)])
#=> [(1, 3), (13, 15), (2, 4), (12, 14)]

First, it sorts the intervals by ending time, than for each interval compares the initial time with the biggest ending time found, and if it's smaller it means that there is an overlap.

The sorting part is the one that requires the most time, so the final complexity is N*log(N).

---

You can go over the list once and keep a hash table of all the intervals encountered so far. If an input interval is part of some interval from the hash table, merge it into the hash table interval. Mark the non-primitive intervals (merged intervals that consist of more than one interval).

Then you go over the list a second time, and for each interval check in the hash table whether it's contained in a merged interval or not.

I don't know if it's O(N), but it's much better than O(N^2).

참고URL : https://stackoverflow.com/questions/4542892/possible-interview-question-how-to-find-all-overlapping-intervals