(1)Merge Intervals
https://leetcode.com/problems/merge-intervals/
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].
思路：贪心思想。首先根据intervals的start进行排序。排完序之后，先将第一个interval加入vector，接着判断之前加入vector的interval和后面一个interval比较。因为是排好序的，所以，只需要判断新的interval的start是否大于前面一个加入vector的interval的end。如果大于，则将后面的interval加入vector，如果不大于，则肯定有交集，两者合并。
struct Interval{
int start;
int end;
Interval():start(),end(){}
Interval(int s,int e):start(s),end(e){}
};
bool cmp(const Interval &left,const Interval & right){
if (left.start == right.start){
return left.end < right.end;
}else{
return left.start < right.start;
}
}
class Solution {
public:
/*struct cmp{
bool operator()(const Interval &left,const Interval & right){
if (left.start == right.start){
return left.end < right.end;
}else{
return left.start < right.start;
}
}
};*/
vector<Interval> merge(vector<Interval> &intervals) {
vector<Interval> result;
if (intervals.size() == || intervals.empty()){
return result;
}
sort(intervals.begin(),intervals.end(),cmp);
result.push_back(intervals[]);
int index = ;
for (int i = ; i < intervals.size(); i++){
if (intervals[i].start <= result[index].end){
int end = max(intervals[i].end,result[index].end);
result[index].end = end;
//index++;
//result.push_back(intervals[i]);
}else{
result.push_back(intervals[i]);
index++;
}
}
return result;
}
};
（2）Insert Interval
https://leetcode.com/problems/insert-interval/
Title：
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].
思路：我最直接的想法就是先找到newInterval的start在哪两个intervals之间，然后再找到end。虽然也能做，但是代码很复杂，不精练
class Solution {
public:
vector<Interval> insert(vector<Interval> & intervals,
Interval newInterval) {
vector<Interval> result;
if (intervals.size() == || intervals.empty()){
result.push_back(newInterval);
return result;
}
int i;
bool flag = false;
for (i = ; i < intervals.size();) {
if (intervals[i].start >= newInterval.start) {
int start, end;
if (i == ) {
start = newInterval.start;
} else {
if (intervals[i-].end >= newInterval.start){
start = intervals[i - ].start;
result.pop_back();
}else
start = newInterval.start;
}
while (i < intervals.size() && intervals[i].start <= newInterval.end) {
i++;
}
if(i == intervals.size()){
end = max(intervals[i-].end,newInterval.end);
Interval interval(start,end);
result.push_back(interval);
}else{
end = max(intervals[i - ].end, newInterval.end);
Interval interval(start, end);
result.push_back(interval);
for (int j = i; j < intervals.size(); j++)
result.push_back(intervals[j]);
}
flag = true;
break;
} else {
result.push_back(intervals[i]);
i++;
}
}
if (!flag){
if (intervals[i-].end < newInterval.start){
//result.push_back(intervals[i-1
result.push_back(newInterval);
}else{
result.pop_back();
int start = intervals[i-].start;
int end = max(intervals[i-].end,newInterval.end);
Interval interval(start,end);
result.push_back(interval);
}
}
return result;
}
};
然后看了网上其他人的想法
Quickly summarize 3 cases. Whenever there is intersection, created a new interval.
遍历一遍vector，根据上述三种情况考虑添加。
vector<Interval> insert(vector<Interval> &intervals, Interval newInterval){
vector<Interval> result;
for (int i = ; i < intervals.size(); i++){
if (intervals[i].end < newInterval.start){
result.push_back(intervals[i]);
}else if (intervals[i].start > newInterval.end){
result.push_back(newInterval);
newInterval = intervals[i];
}else{
newInterval = Interval(min(intervals[i].start,newInterval.start),max(intervals[i].end,newInterval.end));
}
}
result.push_back(newInterval);
return result;
}