检查给定间隔中是否有两个间隔重叠 · GeeksForGeeks 中文系列教程

# 检查给定间隔中是否有两个间隔重叠 > 原文： [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 ```