# 合并重疊間隔 > 原文： [https://www.geeksforgeeks.org/merging-intervals/](https://www.geeksforgeeks.org/merging-intervals/) 給定一組任意時間間隔的時間，將所有重疊的時間間隔合并為一個，并輸出僅具有互斥時間間隔的結果。 為了簡單起見，將間隔表示為整數對。 例如，讓給定的間隔集為{{1,3}，{2,4}，{5,7}，{6,8}}。 間隔{1,3}和{2,4}彼此重疊，因此應將它們合并并成為{1，4}。 同樣，{5，7}和{6，8}應該合并并成為{5，8} 編寫一個函數，該函數為給定間隔集生成合并間隔集。 **簡單方法**是從第一個間隔開始并將其與所有其他間隔進行比較以進行重疊，如果它與任何其他間隔重疊，則從列表中刪除另一個間隔并將另一個合并到第一個間隔中。 首先，對剩余間隔重復相同的步驟。 這種方法無法在比 O（n ^ 2）更好的時間內實現。 **有效方法**是首先根據開始時間對時間間隔進行排序。 獲得排序間隔后，就可以將所有間隔進行線性遍歷。 這個想法是，在間隔的排序數組中，如果 interval [i]不與 interval [i-1]重疊，則 interval [i + 1]就不能與 interval [i-1]重疊，因為 interval [i]的開始時間 +1]必須大于或等于 interval [i]。 以下是詳細的逐步算法。 ``` 1. Sort the intervals based on increasing order of starting time. 2\. Push the first interval on to a stack. 3\. For each interval do the following a. If the current interval does not overlap with the stack top, push it. b. If the current interval overlaps with stack top and ending time of current interval is more than that of stack top, update stack top with the ending time of current interval. 4. At the end stack contains the merged intervals. ``` 以下是上述方法的實現。 ## C++ ```cpp // A C++ program for merging overlapping intervals #include<bits/stdc++.h> using namespace std; // An interval has start time and end time struct Interval { ????int start, end; }; // Compares two intervals according to their staring time. // This is needed for sorting the intervals using library // function std::sort(). See http://goo.gl/iGspV bool compareInterval(Interval i1, Interval i2) { ????return (i1.start < i2.start); } // The main function that takes a set of intervals, merges // overlapping intervals and prints the result void mergeIntervals(Interval arr[], int n) { ????// Test if the given set has at least one interval ????if (n <= 0) ????????return; ????// Create an empty stack of intervals ????stack<Interval> s; ????// sort the intervals in increasing order of start time ????sort(arr, arr+n, compareInterval); ????// push the first interval to stack ????s.push(arr[0]); ????// Start from the next interval and merge if necessary ????for (int i = 1 ; i < n; i++) ????{ ????????// get interval from stack top ????????Interval top = s.top(); ????????// if current interval is not overlapping with stack top, ????????// push it to the stack ????????if (top.end < arr[i].start) ????????????s.push(arr[i]); ????????// Otherwise update the ending time of top if ending of current ????????// interval is more ????????else if (top.end < arr[i].end) ????????{ ????????????top.end = arr[i].end; ????????????s.pop(); ????????????s.push(top); ????????} ????} ????// Print contents of stack ????cout << "\n The Merged Intervals are: "; ????while (!s.empty()) ????{ ????????Interval t = s.top(); ????????cout << "[" << t.start << "," << t.end << "] "; ????????s.pop(); ????} ????return; } // Driver program int main() { ????Interval arr[] =? { {6,8}, {1,9}, {2,4}, {4,7} }; ????int n = sizeof(arr)/sizeof(arr[0]); ????mergeIntervals(arr, n); ????return 0; } ``` ## Java ```java // A Java program for merging overlapping intervals import java.util.Arrays; import java.util.Comparator; import java.util.Stack; public class MergeOverlappingIntervals { ????// The main function that takes a set of intervals, merges? ????// overlapping intervals and prints the result? ????public static void mergeIntervals(Interval arr[])? ????{? ????????// Test if the given set has at least one interval? ????????if (arr.length <= 0)? ????????????return;? ????????// Create an empty stack of intervals? ????????Stack<Interval> stack=new Stack<>(); ????????// sort the intervals in increasing order of start time? ????????Arrays.sort(arr,new Comparator<Interval>(){ ????????????public int compare(Interval i1,Interval i2) ????????????{ ????????????????return i1.start-i2.start; ????????????} ????????}); ????????// push the first interval to stack? ????????stack.push(arr[0]);? ????????// Start from the next interval and merge if necessary? ????????for (int i = 1 ; i < arr.length; i++)? ????????{? ????????????// get interval from stack top? ????????????Interval top = stack.peek();? ????????????// if current interval is not overlapping with stack top,? ????????????// push it to the stack? ????????????if (top.end < arr[i].start)? ????????????????stack.push(arr[i]);? ????????????// Otherwise update the ending time of top if ending of current? ????????????// interval is more? ????????????else if (top.end < arr[i].end)? ????????????{? ????????????????top.end = arr[i].end;? ????????????????stack.pop();? ????????????????stack.push(top);? ????????????}? ????????}? ????????// Print contents of stack? ????????System.out.print("The Merged Intervals are: "); ????????while (!stack.isEmpty())? ????????{? ????????????Interval t = stack.pop();? ????????????System.out.print("["+t.start+","+t.end+"] "); ????????}?? ????}?? ????public static void main(String args[]) { ????????Interval arr[]=new Interval[4]; ????????arr[0]=new Interval(6,8); ????????arr[1]=new Interval(1,9); ????????arr[2]=new Interval(2,4); ????????arr[3]=new Interval(4,7); ????????mergeIntervals(arr); ????} } class Interval { ????int start,end; ????Interval(int start, int end) ????{ ????????this.start=start; ????????this.end=end; ????} } // This code is contributed by Gaurav Tiwari? ``` Output: ``` The Merged Intervals are: [1,9] ``` 該方法的時間復雜度是 O（nLogn），用于排序。 對間隔數組進行排序后，合并將花費線性時間。 **`O(N log N)`和`O(1)`額外空間解決方案** 上述解決方案需要`O(n)`額外的堆棧空間。 通過就地進行合并操作，我們可以避免使用額外的空間。 以下是詳細步驟。 ``` 1) Sort all intervals in decreasing order of start time. 2) Traverse sorted intervals starting from first interval, do following for every interval. a) If current interval is not first interval and it overlaps with previous interval, then merge it with previous interval. Keep doing it while the interval overlaps with the previous one. b) Else add current interval to output list of intervals. ``` 請注意，如果按開始時間的降序對時間間隔進行排序，則可以通過比較前一個時間間隔的開始時間與當前時間間隔的結束時間來快速檢查時間間隔是否重疊。 下面是上述算法的實現。 ## C++ ``` // C++ program to merge overlapping Intervals in? // O(n Log n) time and O(1) extra space.? #include<bits/stdc++.h>? using namespace std;? // An Interval? struct Interval? {? ????int s, e;? };? // Function used in sort? bool mycomp(Interval a, Interval b)? { return a.s < b.s; }? void mergeIntervals(Interval arr[], int n)? {? ????// Sort Intervals in increasing order of ????// start time ????sort(arr, arr+n, mycomp);? ????int index = 0; // Stores index of last element? ????// in output array (modified arr[])? ????// Traverse all input Intervals? ????for (int i=1; i<n; i++)? ????{? ????????// If this is not first Interval and overlaps? ????????// with the previous one? ????????if (arr[index].e >=? arr[i].s)? ????????{? ???????????????// Merge previous and current Intervals? ????????????arr[index].e = max(arr[index].e, arr[i].e);? ????????????arr[index].s = min(arr[index].s, arr[i].s);? ????????}? ????????else { ????????????arr[index] = arr[i];? ????????????index++; ????????}???? ????}? ????// Now arr[0..index-1] stores the merged Intervals? ????cout << "\n The Merged Intervals are: ";? ????for (int i = 0; i <= index; i++)? ????????cout << "[" << arr[i].s << ", " << arr[i].e << "] ";? }? // Driver program? int main()? {? ????Interval arr[] = { {6,8}, {1,9}, {2,4}, {4,7} };? ????int n = sizeof(arr)/sizeof(arr[0]);? ????mergeIntervals(arr, n);? ????return 0;? }? ```