# 檢查是否有任何間隔完全重疊 > 原文： [https://www.geeksforgeeks.org/check-interval-completely-overlaps/](https://www.geeksforgeeks.org/check-interval-completely-overlaps/) 間隔表示為開始時間和結束時間的組合。 給定一組間隔，我們需要編寫一個程序來檢查是否有任何間隔**完全與**重疊。 例子： ``` Input: arr[] = {{1, 3}, {1, 7}, {4, 8}, {2, 5}} Output: true The intervals {1, 3} completely overlaps in {1, 7}. Input: arr[] = {{1, 3}, {7, 9}, {4, 6}, {10, 13}} Output: false No pair of intervals overlap. ``` **簡單解決方案**是考慮每對間隔，并檢查該對是否重疊。 該解決方案的時間復雜度為 `O(n^2)`。 **更好的解決方案**是使用**排序**。 以下是完整的算法。 1）按照開始時間的升序對所有間隔進行排序。 此步驟花費 **O（n Logn）**時間。 2）在排序數組中，如果一個間隔的結束時間不超過前一個間隔的結束，則存在完全重疊。 此步驟花費 **`O(n)`**時間。 以下是上述方法的實現： ``` // A C++ program to check if any two intervals // completely overlap #include <bits/stdc++.h> 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(). bool compareInterval(Interval i1, Interval i2) { ????return (i1.start < i2.start) ? true : false; } // Function to check if any two intervals? // completely overlap bool isOverlap(Interval arr[], int n) { ????// Sort intervals in increasing order of ????// start time ????sort(arr, arr + n - 1, compareInterval); ????// In the sorted array, if end time of an? ????// interval is not more than that of ????// end of previous interval, then there ????// is an overlap ????for (int i = 1; i < n; i++) ????????if (arr[i].end <= arr[i - 1].end) ????????????return true; ????// If we reach here, then no overlap ????return false; } // Driver code int main() { ????// 1st example ????Interval arr1[] = { { 1, 3 }, { 1, 7 }, { 4, 8 },? ??????????????????????????????????????????{ 2, 5 } }; ????int n1 = sizeof(arr1) / sizeof(arr1[0]); ????if (isOverlap(arr1, n1)) ????????cout << "Yes\n"; ????else ????????cout << "No\n"; ????// 2nd example ????Interval arr2[] = { { 1, 3 }, { 7, 9 }, { 4, 6 },? ?????????????????????????????????????????{ 10, 13 } }; ????int n2 = sizeof(arr2) / sizeof(arr2[0]); ????if (isOverlap(arr2, n2)) ????????cout << "Yes\n"; ????else ????????cout << "No\n"; ????return 0; } ``` 輸出： ``` Yes No ``` * * * * * *