# Merge-Intervals

Oct 17, 2017

emmm，又是一道10分钟刷完的题目——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].

• 先对intervalsstart排序
• 将第一个元素放入ret，因为这时start是最小的，我们现在只需要寻找end即可
• 我们考察第二个元素，如果第二个元素的start小于第一个元素的end，我们就将修改end,并考察第三个元素，如果不成立，说明当前元素的end就已经找到了（因为start < end
vector<Interval> merge1(vector<Interval>& intervals) {
if (intervals.size() <= 1) return intervals;

sort(intervals.begin(),intervals.end(),[](const Interval &a,const Interval b) -> bool{
return a.start < b.start;
});

vector<Interval> ret;
ret.push_back(intervals[0]);
int last = 0;

for(int i = 1;i < intervals.size();i++) {
if (ret[last].end >= intervals[i].start)
ret[last].end = max(intervals[i].end,ret[last].end);
else {
ret.push_back(intervals[i]);
last++;
}
}

return ret;
}


public List<Interval> merge(List<Interval> intervals) {
// sort start&end
int n = intervals.size();
int[] starts = new int[n];
int[] ends = new int[n];
for (int i = 0; i < n; i++) {
starts[i] = intervals.get(i).start;
ends[i] = intervals.get(i).end;
}
Arrays.sort(starts);
Arrays.sort(ends);
// loop through
List<Interval> res = new ArrayList<Interval>();
for (int i = 0, j = 0; i < n; i++) { // j is start of interval.
if (i == n - 1 || starts[i + 1] > ends[i]) {