检查任何间隔是否完全重叠-yiteyi-C++库

间隔表示为开始时间和结束时间的组合。给定一组区间，我们需要编写一个程序来检查是否有任何区间 彻底地 相互重叠。

null

例如：

Input:  arr[] = {{1, 3}, {1, 7}, {4, 8}, {2, 5}}Output: trueThe intervals {1, 3} completely overlaps in {1, 7}. Input:  arr[] = {{1, 3}, {7, 9}, {4, 6}, {10, 13}}Output: falseNo pair of intervals overlap.

推荐：请尝试你的方法 {IDE} 首先，在进入解决方案之前。

A. 简单解决方案 是考虑每一对间隔，并检查这对是否重叠。该解的时间复杂度为O（n） ^2. ).

A. 更好的解决方案 就是使用分类 .以下是完整的算法。 1）按开始时间的递增顺序对所有间隔进行排序。这一步需要 O（n Logn） 时间 2）在排序数组中，如果某个间隔的结束时间不超过前一个间隔的结束时间，则存在完全重叠。这一步需要 O（n） 时间

以下是上述方法的实施：

C++

                         // 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 starting                       
                         // 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"                                     ;                       
                                                 else                       
                                                 cout <<                                     "No"                                     ;                       
           
                                                 // 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"                                     ;                       
                                                 else                       
                                                 cout <<                                     "No"                                     ;                       
           
                                                 return                                     0;                       
                         }                       

Javascript

                         <script>                       
                                                 // A JavaScript program to check if any two intervals                       
                                                 // completely overlap                       
           
                                                 // An interval has start time and end time                       
           
                                                 // Compares two intervals according to their starting                       
                                                 // time. This is needed for sorting the intervals                       
                                                 // using library function std::sort().                       
                                                 const compareInterval = (i1, i2) => i1.start - i2.start;                       
           
                                                 // Function to check if any two intervals                       
                                                 // completely overlap                       
                                                 const isOverlap = (arr, n) => {                       
                                   
                                                 // Sort intervals in increasing order of                       
                                                 // start time                       
                                                 arr.sort(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                                     (let 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                       
           
                                                 // 1st example                       
                                                 let arr1 = [                       
                                                 { start: 1, end: 3 },                       
                                                 { start: 1, end: 7 },                       
                                                 { start: 4, end: 8 },                       
                                                 { start: 2, end: 5 }                       
                                                 ];                       
                                                 let n1 = arr1.length;                       
                                                 if                                     (isOverlap(arr1, n1))                       
                                                 document.write(                                     "Yes<br/>"                                     );                       
                                                 else                       
                                                 document.write(                                     "No<br/>"                                     );                       
           
                                                 // 2nd example                       
                                                 let arr2 = [                       
                                                 { start: 1, end: 3 },                       
                                                 { start: 7, end: 9 },                       
                                                 { start: 4, end: 6 },                       
                                                 { start: 10, end: 13 }                       
                                                 ];                       
                                                 let n2 = arr2.length;                       
                                                 if                                     (isOverlap(arr2, n2))                       
                                                 document.write(                                     "Yes<br/>"                                     );                       
                                                 else                       
                                                 document.write(                                     "No<br/>"                                     );                       
           
                                                 // This code is contributed by rakeshsahni                       
           
                         </script>                       

输出：

YesNo

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章