병합 간격-정렬을 사용하여 겹치는 간격 병합

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

Twitter Facebook 링크드인 버퍼 레딧 텀블러

병합 간격 문제에서 우리는 [l, r] 형식의 간격 집합을 제공하고 겹치는 간격을 병합합니다.

차례

예

입력
{[1, 3], [2, 6], [8, 10], [15, 18]}
산출
{[1, 6], [8, 10], [15, 18]}

핀

입력
{[1, 4], [1, 5]}
산출
{[1, 5]}

병합 간격에 대한 순진한 접근 방식

순진한 접근 방식 합병 간격은 단순히 모든 간격을 나머지 모든 간격과 비교하는 것입니다. 교차점이 있으면 두 번째 부분을 제거하고 첫 번째 부분에 병합합니다.

의사 코드

l []는 모든 구간의 하한 (시작점)을, r []는 모든 구간의 상한 (종료점)을 나타냅니다.

int n = total number of intervals
for (int i = 0; i < n; i++) {
  // Removed interval
  if (l[i] == -infinity && r[i] == -infinity) {
    continue;
  }
  for (int j = 0; j < n; j++) {
    // Do not compare with itself
    if (i == j)
      continue;
    // Do not compare with removed intervals
    if (l[i] == infinity && r[i] == -infinity) {
      continue;
    }
    // Check if there is some intersection point	
    if ((l[j] >= l[i] && l[j] <= r[i]) || (r[j] >= l[i] && r[j] <= r[i])) {
      // Merge the intervals
      l[i] = min(l[i], l[j])
      r[i] = min(r[i], r[j])
      // Remove the other interval
      l[j] = -infinity
      r[j] = -infinity
    } else {
      // Do not merge
    }
  }
}
// Print the merged intervals
for (int i = 0; i < n; i++) {
  if (!(l[i] == -infinity && r[i] == -infinity)) {
    print(l[i] + " " + r[i]);
  }
}

시간 복잡성 = O (n ^ 2) 여기서 n은 주어진 간격의 수입니다. 여기서는 N * N 시간이 걸리는 간격의 각 쌍을 확인합니다.

JAVA 코드

public class MergingIntervals {
    // Function to merge the intervals and print merged intervals
    private static void mergeIntervals(Interval intervals[]) {
        int n = intervals.length;
        for (int i = 0; i < n; i++) {
            // Removed intervals
            if (intervals[i].l == Integer.MIN_VALUE
                    && intervals[i].r == Integer.MIN_VALUE) {
                continue;
            }
            for (int j = 0; j < n; j++) {
                // Do not compare with itself
                if (i == j)
                    continue;
                // Do not compare with removed intervals
                if (intervals[i].l == Integer.MIN_VALUE
                        && intervals[i].r == Integer.MIN_VALUE) {
                    continue;
                }
                // Check if there is some intersection point
                if ((intervals[j].l >= intervals[i].l && intervals[j].l <= intervals[i].r) ||
                        intervals[j].r >= intervals[i].l && intervals[j].r <= intervals[i].r) {
                    // Merge the intervals
                    intervals[i].l = Math.min(intervals[j].l, intervals[i].l);
                    intervals[i].r = Math.max(intervals[j].r, intervals[i].r);
                    // Remove the other interval
                    intervals[j].l = Integer.MIN_VALUE;
                    intervals[j].r = Integer.MIN_VALUE;
                } else {
                    // Do not merge
                }
            }
        }

        // Print the merged intervals
        for (int i = 0; i < n; i++) {
            if (!(intervals[i].l == Integer.MIN_VALUE && intervals[i].r == Integer.MIN_VALUE)) {
                System.out.println(intervals[i].l + " " + intervals[i].r);
            }
        }
    }

    public static void main(String[] args) {
        // Example 1
        Interval intervals[] = new Interval[4];
        intervals[0] = new Interval(1, 3);
        intervals[1] = new Interval(2, 6);
        intervals[2] = new Interval(8, 10);
        intervals[3] = new Interval(15, 18);

        mergeIntervals(intervals);

        // Example 2
        Interval intervals2[] = new Interval[2];
        intervals2[0] = new Interval(1, 4);
        intervals2[1] = new Interval(1, 5);

        mergeIntervals(intervals2);
    }

    // Class representing an interval
    static class Interval {
        int l;      // Staring point
        int r;      // Ending point

        public Interval(int l, int r) {
            this.l = l;
            this.r = r;
        }

        // Comparator to sort the intervals
        public static final Comparator<Interval> comp = new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                int l1 = o1.l;
                int l2 = o2.l;
                int r1 = o1.r;
                int r2 = o2.r;

                if (l1 == l2) {
                    return Integer.compare(r1, r2);
                }

                return Integer.compare(l1, l2);
            }
        };
    }
}

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

// Structure representing an interval
struct Interval {
    int l, r;
};

// Function to merge the intervals and print merged intervals
void mergeIntervals(Interval intervals[], int n) {
    for (int i = 0; i < n; i++) {
        // Removed intervals
        if (intervals[i].l == INT_MIN && intervals[i].r == INT_MIN) {
            continue;
        }
        for (int j = 0; j < n; j++) {
            // Do not compare with itself
            if (j == i) {
                continue;
            }
            // Do not compare with removed intervals
            if (intervals[i].l == INT_MIN && intervals[i].r == INT_MIN) {
                continue;
            }
            // Check if there is some intersection point
            if ((intervals[j].l >= intervals[i].l && intervals[j].l <= intervals[i].r) || (intervals[j].r >= intervals[i].l && intervals[j].r <= intervals[i].r)) {
                // Merge the intervals
                intervals[i].l = std::min(intervals[i].l, intervals[j].l);
                intervals[i].r = std::max(intervals[i].r, intervals[j].r);
                // Remove the other interval
                intervals[j].l = INT_MIN;
                intervals[j].r = INT_MIN;
            } else {
                // Do not merge
            }
        }
    }
    
    // Print the merged intervals
    for (int i = 0; i < n; i++) {
        if (!(intervals[i].l == INT_MIN && intervals[i].r == INT_MIN)) {
            cout<<intervals[i].l<<" "<<intervals[i].r<<endl;
        }
    }
}

int main() {
    // Example 1
    Interval intervals[] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    
    int n1 = sizeof(intervals) / sizeof(intervals[0]);

    mergeIntervals(intervals, n1);

    // Example 2
    Interval intervals2[] = {{1, 4}, {1, 5}};
    
    int n2 = sizeof(intervals2) / sizeof(intervals2[0]);

    mergeIntervals(intervals2, n2);
    
    return 0;
}

{[1, 4], [1, 5]}

{[1, 5]}

병합 간격을위한 최적의 접근 방식

병합 간격에 대한 최적의 방법은 두 간격의 시작점이 동일한 경우 시작점 (하한)에 따라 간격을 오름차순으로 정렬하는 것입니다. 종류 종료 지점에 따라 오름차순으로 정렬합니다. 이렇게하면 몇 가지 공통 지점이있을 수있는 간격이 차례로 발생합니다. 정렬 후 순진한 접근 방식에서와 같이 인접한 간격을 비교하고 병합합니다.

예

원래 간격 : {[5, 8], [3, 6], [15, 25], [10, 14], [9, 13]}
정렬 후 : {[[3, 6], [5, 8], [9, 13], [10, 14], [15, 25]}
이 예에서는 정렬 후 교차 구간이 나란히 있음이 분명하므로 인접한 구간을 비교하기 만하면됩니다.
[3, 6] 및 [5, 8]이 [3, 8]로 병합됩니다.
[9, 14] 및 [10, 14]이 [9, 14]로 병합됩니다.
산출 : {[3, 8], [9, 14], [15, 25]}

의사 코드

l [] –> 모든 구간의 하한 (시작점)
r [] –> 모든 구간의 상한 (종료점)
n –> 총 간격 수

Sort l and r as described.
for (int i = 0; i < n - 1; i++) {
  // Compare i and (i + 1)th intervals
  if ((l[i] >= l[i + 1] && l[i] <= r[i + 1]) || (r[i] >= l[i + 1] && r[i] <= r[i + 1])) {
    // Merge intervals
    l[i + 1] = min(l[i], l[i + 1])
    r[i + 1] = max(r[i], r[i + 1])
    // Remove the previous interval
    l[i] = -infinity
    r[i] = -infinity
  }
}
// Print the merged intervals
for (int i = 0; i < n; i++) {
  if (!(l[i] == -infinity && r[i] == -infinity)) {
    // Print only non removed intervals
    print(l[i] + " " + r[i])
  }
}

시간 복잡성 = O (n * 로그 (n)) 여기서 n은 주어진 간격의 수입니다. 정렬 시간이 오래 걸리는 정렬 기능을 사용합니다.

JAVA 코드

public class MergingIntervals {
    // Function to merge the intervals and print merged intervals
    private static void mergeIntervals(Interval intervals[]) {
        // Sort the intervals array
        Arrays.sort(intervals, Interval.comp);

        // Traverse the sorted array
        for (int i = 0; i < intervals.length - 1; i++) {
            // Compare i and (i + 1)th intervals
            if ((intervals[i].l >= intervals[i + 1].l && intervals[i].l <= intervals[i + 1].r)
                    || (intervals[i].r >= intervals[i + 1].l && intervals[i].r <= intervals[i + 1].r)) {
                // Merge intervals
                intervals[i + 1].l = Math.min(intervals[i].l, intervals[i + 1].l);
                intervals[i + 1].r = Math.max(intervals[i].r, intervals[i + 1].r);
                // Remove previous interval
                intervals[i].l = Integer.MIN_VALUE;
                intervals[i].r = Integer.MIN_VALUE;
            } else {
                // Do not merge
            }
        }

        // Print the merged intervals
        for (int i = 0; i < intervals.length; i++) {
            if (!(intervals[i].l == Integer.MIN_VALUE && intervals[i].r == Integer.MIN_VALUE)) {
                System.out.println(intervals[i].l + " " + intervals[i].r);
            }
        }
    }

    public static void main(String[] args) {
        // Example 1
        Interval intervals[] = new Interval[4];
        intervals[0] = new Interval(1, 3);
        intervals[1] = new Interval(2, 6);
        intervals[2] = new Interval(8, 10);
        intervals[3] = new Interval(15, 18);

        mergeIntervals(intervals);

        // Example 2
        Interval intervals2[] = new Interval[2];
        intervals2[0] = new Interval(1, 4);
        intervals2[1] = new Interval(1, 5);

        mergeIntervals(intervals2);
    }

    // Class representing an interval
    static class Interval {
        int l;      // Staring point
        int r;      // Ending point

        public Interval(int l, int r) {
            this.l = l;
            this.r = r;
        }

        // Comparator to sort the intervals
        public static final Comparator<Interval> comp = new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                int l1 = o1.l;
                int l2 = o2.l;
                int r1 = o1.r;
                int r2 = o2.r;

                if (l1 == l2) {
                    return Integer.compare(r1, r2);
                }

                return Integer.compare(l1, l2);
            }
        };
    }
}

C ++ 코드

#include <bits/stdc++.h>
using namespace std;

// Structure representing an interval
struct Interval {
    int l, r;
};

// Comparator for sorting intervals
bool compareInterval(Interval i1, Interval i2) {
    if (i1.l == i2.l) {
        return (i1.r < i2.r);
    }
    return (i1.l < i2.l);
}

// Function to merge the intervals and print merged intervals
void mergeIntervals(Interval intervals[], int n) {
    // Sort the intervals array
    sort(intervals, intervals + n, compareInterval);
    
    // Traverse the sorted array
    for (int i = 0; i < n - 1; i++) {
        // Compare i and (i + 1)th intervals
        if ((intervals[i].l >= intervals[i + 1].l && intervals[i].l <= intervals[i + 1].r) || (intervals[i].r >= intervals[i + 1].l && intervals[i].r <= intervals[i + 1].r)) {
            // Merge intervals
            intervals[i + 1].l = std::min(intervals[i].l, intervals[i + 1].l);
            intervals[i + 1].r = std::max(intervals[i].r, intervals[i + 1].r);
            // Remove previous interval
            intervals[i].l = INT_MIN;
            intervals[i].r = INT_MIN;
        } else {
            // Do not merge
        }
    }
    
    // Print the merged intervals
    for (int i = 0; i < n; i++) {
        if (!(intervals[i].l == INT_MIN && intervals[i].r == INT_MIN)) {
            cout<<intervals[i].l<<" "<<intervals[i].r<<endl;
        }
    }
}

int main() {
    // Example 1
    Interval intervals[] = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
    
    int n1 = sizeof(intervals) / sizeof(intervals[0]);

    mergeIntervals(intervals, n1);

    // Example 2
    Interval intervals2[] = {{1, 4}, {1, 5}};
    
    int n2 = sizeof(intervals2) / sizeof(intervals2[0]);

    mergeIntervals(intervals2, n2);
    
    return 0;
}

{[5, 8], [3, 6], [15, 25], [10, 14], [9, 13]}

{[3, 8], [9, 14], [15, 25]}

참조

Twitter Facebook 링크드인 버퍼 레딧 텀블러