首页 > 代码库 > 区间合并问题
区间合并问题
【LeetCode】57. Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].
Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].
This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
思路：
由于insert和erase代价太大，需要移动后面所有元素。
所有空间换时间，返回新的数组ret，而不采用inplace做法。
主要以下三种情况：
1、newInterval与当前interval没有交集，则按照先后次序加入newInterval和当前interval，然后装入所有后续interval。返回ret。
2、newInterval与当前interval有交集，合并成为新的newInterval，然后处理后续interval。
3、处理完最后一个interval若仍未返回ret，说明newInterval为最后一个interval，装入ret。返回ret。
代码如下：
1 /** 2 * Definition for an interval. 3 * struct Interval { 4 * int start; 5 * int end; 6 * Interval() : start(0), end(0) {} 7 * Interval(int s, int e) : start(s), end(e) {} 8 * }; 9 */ 10 class Solution { 11 public: 12 vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { 13 vector<Interval> ret; 14 if(intervals.empty()) 15 { 16 ret.push_back(newInterval); 17 return ret; 18 } 19 20 int i = 0; 21 while(i < intervals.size()) 22 { 23 //no overlapping 24 if(newInterval.end < intervals[i].start) 25 { 26 ret.push_back(newInterval); 27 while(i < intervals.size()) 28 { 29 ret.push_back(intervals[i]); 30 i ++; 31 } 32 return ret; 33 } 34 else if(newInterval.start > intervals[i].end) 35 ret.push_back(intervals[i]); 36 //overlapping 37 else 38 { 39 newInterval.start = min(newInterval.start, intervals[i].start); 40 newInterval.end = max(newInterval.end, intervals[i].end); 41 } 42 i ++; 43 } 44 ret.push_back(newInterval); 45 return ret; 46 } 47 };
【LeetCode】56. Merge Interval
Given a collection of intervals, merge all overlapping intervals.
For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].
思路：
解法一：
我们首先要做的就是给区间集排序，由于我们要排序的是个结构体，所以我们要定义自己的comparator，才能用sort来排序，我们以start的值从小到大来排序，排完序我们就可以开始合并了，首先把第一个区间存入结果中，然后从第二个开始遍历区间集，如果结果中最后一个区间和遍历的当前区间无重叠，直接将当前区间存入结果中，如果有重叠，将结果中最后一个区间的end值更新为结果中最后一个区间的end和当前end值之中的较大值，然后继续遍历区间集，以此类推可以得到最终结果，代码如下：
1 class Solution { 2 public: 3 static bool comp(const Interval &a, const Interval &b) { 4 return (a.start < b.start); 5 } 6 vector<Interval> merge(vector<Interval> &intervals) { 7 vector<Interval> res; 8 if (intervals.empty()) return res; 9 sort(intervals.begin(), intervals.end(), comp); 10 res.push_back(intervals[0]); 11 for (int i = 1; i < intervals.size(); ++i) { 12 if (res.back().end >= intervals[i].start) { 13 res.back().end = max(res.back().end, intervals[i].end); 14 } else { 15 res.push_back(intervals[i]); 16 } 17 } 18 return res; 19 } 20 };
解法二：
直接调用了之前那道题 Insert Interval 插入区间 的函数，由于插入的过程中也有合并的操作，所以我们可以建立一个空的集合，然后把区间集的每一个区间当做一个新的区间插入结果中，也可以得到合并后的结果，代码如下：
1 class Solution { 2 public: 3 vector<Interval> merge(vector<Interval> &intervals) { 4 vector<Interval> res; 5 for (int i = 0; i < intervals.size(); ++i) { 6 res = insert(res, intervals[i]); 7 } 8 return res; 9 } 10 vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) { 11 vector<Interval> res = intervals; 12 vector<Interval>::iterator it = res.begin(); 13 int overlap = 0; 14 while(it != res.end()) { 15 if(newInterval.end < it->start) break; 16 else if(newInterval.start > it->end) {} 17 else { 18 newInterval.start = min(newInterval.start, it->start); 19 newInterval.end = max(newInterval.end, it->end); 20 ++overlap; 21 } 22 ++it; 23 } 24 if(overlap != 0) it = res.erase(it-overlap, it); 25 res.insert(it, newInterval); 26 return res; 27 } 28 };
3.找出重叠区间的个数
题目描述：
给定多个可能重叠的区间，找出重叠区间的个数。
举例如下：
输入：[1，5]，[10，15]，[5，10]，[20，30]
输出：2
说明：题意应该是找出重叠区间中区间的最大个数，当没有区间重叠时，重叠个数最大为1，比如
输入为：[1，5]，[10，15]，则输出为1；
输入为：[1，2]，[2，3]，[3，4]，[4，5]，则输出为2（重叠区间相互之间都要有交集）；
输入为：[1，7]，[2，5]，[3，4]，[8，15]，[9，17]，[20，25]，则输出为3。
题目分析：
此题解题方法比较简单，只要将区间分隔成各个点，每个点有两个属性，一个是值，一个是标志（0起点，1止点），然后对这些点排序，最后，从头开始扫描排序的结果，遇到起点重叠个数加1，遇到止点重叠个数减1，并且记录好重叠个数的最大值。
本算法的时间复杂度为O(nlogn)，因为算法时间主要消耗在排序上。
代码如下：
1 //区间定义 2 class Interval 3 { 4 public: 5 Interval( int iStart, int iEnd) 6 :m_iStart( iStart), m_iEnd(iEnd){} 7 int m_iStart; 8 int m_iEnd; 9 }; 10 11 typedef vector<Interval> IntervalVec; 12 13 14 //区间拆分的点定义 15 class PointComparable 16 { 17 public: 18 PointComparable( int iVal, int iType ) 19 :m_iVal( iVal ), m_iType( iType ){} 20 21 //重载小于操作符，排序使用 22 bool operator < ( const PointComparable& pcPoint ) 23 { 24 if ( this->m_iVal == pcPoint.m_iVal ) 25 { 26 return this->m_iType < pcPoint.m_iType; 27 } 28 return this->m_iVal < pcPoint.m_iVal; 29 } 30 31 int m_iVal; 32 int m_iType;//点类型，0为起点，1为终点 33 }; 34 35 int GetOverlappedIntervalMaxCount( const IntervalVec& intvVec ) 36 { 37 vector<PointComparable> pcVec; 38 for ( IntervalVec::const_iterator it = intvVec.begin(); 39 it != intvVec.end(); ++it ) 40 { 41 pcVec.push_back( PointComparable( it->m_iStart, 0 ) ); 42 pcVec.push_back( PointComparable( it->m_iEnd, 1 ) ); 43 } 44 45 sort( pcVec.begin(), pcVec.end() ); 46 47 48 49 int iMaxCount = 0; 50 int iCurCount = 0; 51 for ( vector<PointComparable>::iterator itTemp = pcVec.begin(); 52 itTemp != pcVec.end(); ++itTemp ) 53 { 54 cout << itTemp->m_iVal << " " << itTemp->m_iType << endl; 55 if ( itTemp->m_iType == 0 ) 56 { 57 iCurCount++; 58 iMaxCount = __max( iCurCount, iMaxCount ); 59 } 60 else 61 { 62 iCurCount--; 63 } 64 } 65 66 return iMaxCount; 67 }
区间合并问题