leetcode 中的两个集合操作题目：
56 Merge Intervals – leetcode
题目描述：
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].
分析：
集合的定义为：
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/因为给定的集合不一定有序，我们按照集合开始值（start）的大小对其进行排序，得到有序后的集合后，相邻两个区间 i-1 和 i一定有如下关系：有以下特征：
（1）intervals[i-1].start <= intervals[i].start;
（2）如果 intervals[i-1].end >= intervals[i].start; 此时，区间有相交的部分，需要合并；
（3）如果 intervals[i-1].end < intervals[i].start; 则i-1，i 不可合并，且 i-1 与 i 之后的区间也不可能合并。因为intervals[i-1].end
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
vector<Interval> ans;
if (intervals.size() == 0) return ans;
//排序（左区间从小到大排序）
sort(intervals.begin(), intervals.end(), Solution::comp);
//初始化新的区间的开始值和结束值
int nowStart = intervals[0].start;
int nowEnd = intervals[0].end;
for (int i=1; i<intervals.size(); ++i){
if (nowEnd >= intervals[i].start){//合并，若intervals[i-1].end >= intervals[i].start，则这两个区间可以合并成[intervals[i-1].start, intervals[i].end]
if (nowEnd < intervals[i].end) //再次判断下，左区间的结束值是否小于右区间的结束值
nowEnd = intervals[i].end;
}else{// 当前区间与区间i不重叠，则当前区间不可再扩张，需要将当前的区间保存，并重新初始化新的区间开始值和结束值
ans.push_back(Interval(nowStart, nowEnd));//保存当前区间
nowStart = intervals[i].start;
nowEnd = intervals[i].end;
}
}
//保存最后一次新的区间
ans.push_back(Interval(nowStart, nowEnd));
return ans;
}
//以左区间从小到大排序
static bool comp(Interval x, Interval y){
return x.start < y.start || (x.start == y.start && x.end < y.end);
}
};
57 Insert Interval – leetcode
题目描述：
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].
分析：
- 插入后，区间才可能变化，之前的区间一定没有交叉重复的部分；
- 插入后，将若干个区间合并成一个区间，这些合并的区域一定是连续的；
- 对于不需要合并的区域，依次将其添加到结果中即可，这些不需要合并的区间一定集中的头部和尾部；
3.1）左半部分：从头开始，依次向后遍历，如果原区间的 end 值，小于插入区间的开始值（start），那么这个区间不需要合并，遍历下一个；
3.2）右半部分：从尾部开始，依次向前遍历，如果原区间的 start 值，大于新插入区间的结束值 （end），那么这个区间不需要合并； - 对于需要合并的区间，找出新的开始值（start）和结束值（end）；
4.1）新的开始值为：第一个与新插入区间有交集的区间的开始值 与 新插入区间的的开始值 的最小值；
4.2）新的结束值为：最后一个与新插入区间有交集的区间的结束值 与 新插入区间的结束值 的最大值； - 从左到右依次将原区间和新区间放入结果中。
代码：
class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
int len = intervals.size();
//找出不需要合并的集合(集中在首部和尾部)
int l = -1, r = len;
//找出左半部分不需要合并的区间
while(l < len - 1 && intervals[l+1].end < newInterval.start) ++l;
//找出右半部分不需要合并的区间
while(r > 0 && intervals[r-1].start > newInterval.end) --r;
//合并区间部分，找出开始值和结束值
//开始值 = 最小值（插入区间， 第一个有交集的区间）
if (l < len -1) newInterval.start = min(intervals[l+1].start, newInterval.start);
//结束值 = 最大值（插入区间， 最后一个有交集的区间）
if (r > 0) newInterval.end = max(intervals[r-1].end, newInterval.end);
// 按照左到右的顺序对区间进行保存
vector<Interval> ans;
//左半部分的不需要合并的区间
for (int i=0; i<=l; ++i) ans.push_back(intervals[i]);
//新插入区间（中间合并区间）
ans.push_back(newInterval);
//右半部分的不需要合并的区间
for (int i=r; i<len; ++i) ans.push_back(intervals[i]);
return ans;
}
};