# 檢查給定間隔中是否有兩個間隔重疊 > 原文： [https://www.geeksforgeeks.org/check-if-any-two-intervals-overlap-among-a-given-set-of-intervals/](https://www.geeksforgeeks.org/check-if-any-two-intervals-overlap-among-a-given-set-of-intervals/) 間隔表示為開始時間和結束時間的組合。 給定一組間隔，請檢查是否有兩個間隔重疊。 **示例**： ``` Input: arr[] = {{1, 3}, {5, 7}, {2, 4}, {6, 8}} Output: true The intervals {1, 3} and {2, 4} overlap Input: arr[] = {{1, 3}, {7, 9}, {4, 6}, {10, 13}} Output: false No pair of intervals overlap. ``` 預期的時間復雜度為 O（nLogn），其中 n 是間隔數。 **我們強烈建議您最小化您的瀏覽器，然后自己嘗試。** **簡單解決方案**是考慮每對間隔，并檢查該對是否重疊。 該解決方案的時間復雜度為 `O(n^2)` **方法 1** 更好的解決方案是**使用排序**。 以下是完整的算法。 1）按照開始時間的升序對所有間隔進行排序。 此步驟需要 O（nLogn）時間。 2）在排序數組中，如果一個間隔的開始時間小于上一個間隔的結束，則存在重疊。 此步驟需要`O(n)`時間。 因此，該算法的總體時間復雜度為 O（nLogn）+`O(n)`，即 O（nLogn）。 下面是上述想法的 C++ 實現。 ``` // A C++ program to check if any two intervals overlap #include <algorithm> #include <iostream> using namespace std; // An interval has start time and end time struct Interval { ????int start; ????int 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) ? true : false; } // Function to check if any two intervals overlap bool isOverlap(Interval arr[], int n) { ????// Sort intervals in increasing order of start time ????sort(arr, arr + n , compareInterval); ????// In the sorted array, if start time of an interval ????// is less than end of previous interval, then there ????// is an overlap ????for (int i = 1; i < n; i++) ????????if (arr[i - 1].end > arr[i].start) ????????????return true; ????// If we reach here, then no overlap ????return false; } // Driver program int main() { ????Interval arr1[] = { { 1, 3 }, { 7, 9 }, { 4, 6 }, { 10, 13 } }; ????int n1 = sizeof(arr1) / sizeof(arr1[0]); ????isOverlap(arr1, n1) ? cout << "Yes\n" : cout << "No\n"; ????Interval arr2[] = { { 6, 8 }, { 1, 3 }, { 2, 4 }, { 4, 7 } }; ????int n2 = sizeof(arr2) / sizeof(arr2[0]); ????isOverlap(arr2, n2) ? cout << "Yes\n" : cout << "No\n"; ????return 0; } ``` 輸出： ``` No Yes ``` **方法 2** ： **Anjali Agarwal** 提出了這種方法。 步驟如下： > 1.找到整體最大元素。 使其為 **max_ele** > 2.初始化一個大小為 max_ele 的數組，值為 0。 > 3.對于每個間隔[start，end]，在索引 start 處增加值，即 arr [start] ++并減小索引（end + 1）處的值，即 arr [end + 1]--。 > 4.計算此數組的前綴和（arr []）。 > 5.此前綴和數組的每個索引 i 都將告訴我在所有間隔中，i 發生了多少次。 如果此值大于 1，則它將以 2 個或更多個間隔出現。 > 6.因此，只需將結果變量初始化為 false，并遍歷前綴求和數組，只要該索引處的值大于 1，就將結果變量更改為 true。 下面是此（方法 2）方法的實現。 ## C++ ```cpp // A C++ program to check if any two intervals overlap #include <algorithm> #include <iostream> using namespace std; // An interval has start time and end time struct Interval { ????int start; ????int end; }; // Function to check if any two intervals overlap bool isOverlap(Interval arr[], int n) { ????int max_ele = 0; ????// Find the overall maximum element ????for (int i = 0; i < n; i++) { ????????if (max_ele < arr[i].end) ????????????max_ele = arr[i].end; ????} ????// Initialize an array of size max_ele ????int aux[max_ele + 1] = { 0 }; ????for (int i = 0; i < n; i++) { ????????// starting point of the interval ????????int x = arr[i].start; ????????// end point of the interval ????????int y = arr[i].end; ????????aux[x]++, aux[y + 1]--; ????} ????for (int i = 1; i <= max_ele; i++) { ????????// Calculating the prefix Sum ????????aux[i] += aux[i - 1]; ????????// Overlap ????????if (aux[i] > 1) ????????????return true; ????} ????// If we reach here, then no Overlap ????return false; } // Driver program int main() { ????Interval arr1[] = { { 1, 3 }, { 7, 9 }, { 4, 6 }, { 10, 13 } }; ????int n1 = sizeof(arr1) / sizeof(arr1[0]); ????isOverlap(arr1, n1) ? cout << "Yes\n" : cout << "No\n"; ????Interval arr2[] = { { 6, 8 }, { 1, 3 }, { 2, 4 }, { 4, 7 } }; ????int n2 = sizeof(arr2) / sizeof(arr2[0]); ????isOverlap(arr2, n2) ? cout << "Yes\n" : cout << "No\n"; ????return 0; } // This Code is written by Anjali Agarwal ```