给定一组任意顺序的时间间隔，将所有重叠的时间间隔合并为一个时间间隔，并输出只应具有互斥时间间隔的结果。为了简单起见，将区间表示为整数对。 例如，假设给定的区间集是{1,3}，{2,4}，{5,7}，{6,8}。区间{1,3}和{2,4}相互重叠，因此它们应该合并成{1,4}。同样地，{5,7}和{6,8}应该合并成{5,8}
null
编写一个函数，为给定的区间集生成合并区间集。 A. 简单方法 就是从第一个间隔开始，将其与所有其他间隔进行比较，以便重叠，如果它与任何其他间隔重叠，则从列表中删除其他间隔，并将其他间隔合并到第一个间隔中。在第一次之后的剩余时间间隔内重复相同的步骤。这种方法不可能在超过O（n^2）的时间内实现。 一 有效的方法 首先根据开始时间对间隔进行排序。一旦我们有了排序的区间，我们就可以将所有区间组合成一个线性遍历。其思想是，在区间的排序数组中，如果区间[i]与区间[i-1]不重叠，那么区间[i+1]就不能与区间[i-1]重叠，因为区间[i+1]的起始时间必须大于或等于区间[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++
// 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 starting 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 << " 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
// 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 |
C#
// A C# program for merging overlapping intervals using System; using System.Collections; using System.Collections.Generic; public class MergeOverlappingIntervals { // sort the intervals in increasing order of start time class sortHelper : IComparer { int IComparer.Compare( object a, object b) { Interval first = (Interval)a; Interval second = (Interval)b; if (first.start == second.start) { return first.end - second.end; } return first.start - second.start; } } // 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 ; Array.Sort(arr, new sortHelper()); // Create an empty stack of intervals Stack stack = new Stack(); // 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 = (Interval)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 Console.Write( "The Merged Intervals are: " ); while (stack.Count != 0) { Interval t = (Interval)stack.Pop(); Console.Write( "[" + t.start + "," + t.end + "] " ); } } // Driver code public static void Main() { 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); } } public class Interval { public int start,end; public Interval( int start, int end) { this .start = start; this .end = end; } } // This code is contributed by rutvik_56. |
输出：
The Merged Intervals are: [1,9]
该方法的时间复杂度为O（nLogn），用于排序。一旦对区间数组进行排序，合并需要线性时间。 O（n logn）和O（1）额外空间解决方案 上述解决方案需要为堆栈增加O（n）个额外空间。我们可以通过就地执行合并操作来避免使用额外的空间。下面是详细的步骤。
1) Sort all intervals in increasing 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); } else { index++; arr[index] = arr[i]; } } // Now arr[0..index-1] stores the merged Intervals cout << " 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; } |
JAVA
// Java program to merge overlapping Intervals in // O(n Log n) time and O(1) extra space import java.util.Arrays; import java.util.Comparator; // An Interval class Interval { int start,end; Interval( int start, int end) { this .start=start; this .end=end; } } public class MergeOverlappingIntervals { // Function that takes a set of intervals, merges // overlapping intervals and prints the result public static void mergeIntervals(Interval arr[]) { // Sort 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; } }); int index = 0 ; // Stores index of last element // in output array (modified arr[]) // Traverse all input Intervals for ( int i= 1 ; i<arr.length; i++) { // If this is not first Interval and overlaps // with the previous one if (arr[index].end >= arr[i].start) { // Merge previous and current Intervals arr[index].end = Math.max(arr[index].end, arr[i].end); } else { index++; arr[index] = arr[i]; } } // Now arr[0..index-1] stores the merged Intervals System.out.print( "The Merged Intervals are: " ); for ( int i = 0 ; i <= index; i++) { System.out.print( "[" + arr[i].start + "," + arr[i].end + "]" ); } } // Driver Code 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); } } // This code is contributed by Gaurav Tiwari // This code was fixed by Subham Mukhopadhyay |
Python3
# Python3 program to merge overlapping Intervals # in O(n Log n) time and O(1) extra space def mergeIntervals(arr): # Sorting based on the increasing order # of the start intervals arr.sort(key = lambda x: x[ 0 ]) # array to hold the merged intervals m = [] s = - 10000 max = - 100000 for i in range ( len (arr)): a = arr[i] if a[ 0 ] > max : if i ! = 0 : m.append([s, max ]) max = a[ 1 ] s = a[ 0 ] else : if a[ 1 ] > = max : max = a[ 1 ] #'max' value gives the last point of # that particular interval # 's' gives the starting point of that interval # 'm' array contains the list of all merged intervals if max ! = - 100000 and [s, max ] not in m: m.append([s, max ]) print ( "The Merged Intervals are :" , end = " " ) for i in range ( len (m)): print (m[i], end = " " ) # Driver code arr = [[ 6 , 8 ], [ 1 , 9 ], [ 2 , 4 ], [ 4 , 7 ]] mergeIntervals(arr) # This code is contributed # by thirumalai srinivasan |
输出：
The Merged Intervals are: [1,9]
感谢Gaurav Ahirwar提出这种方法。
?list=PLqM7alHXFySEQDk2MDfbwEdjd2svVJH9p 本文由拉维·钱德拉·埃纳甘蒂编辑。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
