56. 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].

链接：https://leetcode.com/problems/merge-intervals/#/description

4/18/2017

22%， 34ms

要好好研究Java的sort各种知识，比如comparator, comparable等等，这道题的sort部分很多是参考课件

注意的问题：

1. Arrays.sort()是个array用的，List直接用List.sort()

2. 如何实现compare函数，comparator接口，以及comparator的类

 1 public class Solution {
 2     public List<Interval> merge(List<Interval> intervals) {
 3         intervals.sort(new IntervalComparator());
 4         List<Interval> ret = new ArrayList<Interval>();
 5         int i = -1;
 6         for (Interval interval: intervals) {
 7             if (i == -1) {
 8                 ret.add(interval);
 9                 i++;
10             } else {
11                 if (ret.get(i).end < interval.start) {
12                     ret.add(interval);
13                     i++;
14                 } else if (ret.get(i).end < interval.end) {
15                     Interval tmp = new Interval();
16                     tmp.start = ret.get(i).start;
17                     tmp.end = interval.end;
18                     ret.set(i, tmp);
19                 }
20             }
21         }
22         return ret;
23     }
24     private static class IntervalComparator implements Comparator<Interval> {
25         public int compare(Interval a, Interval b) {
26             if      (a.start < b.start) return -1;
27             else if (a.start > b.start) return +1;
28             else if (a.end < b.end) return -1;
29             else if (a.end > b.end) return +1;
30             else                    return  0;
31         }
32     }
33 }

别人的算法：

这个想法跟我一样，更新ret部分我觉得反而不够清晰，不过可以看如何实现比较

https://discuss.leetcode.com/topic/4319/a-simple-java-solution

 1 public List<Interval> merge(List<Interval> intervals) {
 2     if (intervals.size() <= 1)
 3         return intervals;
 4     
 5     // Sort by ascending starting point using an anonymous Comparator
 6     intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
 7     
 8     List<Interval> result = new LinkedList<Interval>();
 9     int start = intervals.get(0).start;
10     int end = intervals.get(0).end;
11     
12     for (Interval interval : intervals) {
13         if (interval.start <= end) // Overlapping intervals, move the end if needed
14             end = Math.max(end, interval.end);
15         else {                     // Disjoint intervals, add the previous one and reset bounds
16             result.add(new Interval(start, end));
17             start = interval.start;
18             end = interval.end;
19         }
20     }
21     
22     // Add the last interval
23     result.add(new Interval(start, end));
24     return result;
25 }

可以用Collections.sort

1 Collections.sort(intervals, new Comparator<Interval>() {
2         public int compare(Interval i1, Interval i2) {
3             if (i1.start != i2.start) {
4                 return i1.start - i2.start;
5             }
6             return i1.end - i2.end;
7         }
8     });

另外好像比较时候不需要很精细的比较end，这道题里比较start以及足够

https://discuss.leetcode.com/topic/20263/c-10-line-solution-easing-understanding

 1 vector<Interval> merge(vector<Interval>& ins) {
 2     if (ins.empty()) return vector<Interval>{};
 3     vector<Interval> res;
 4     sort(ins.begin(), ins.end(), [](Interval a, Interval b){return a.start < b.start;});
 5     res.push_back(ins[0]);
 6     for (int i = 1; i < ins.size(); i++) {
 7         if (res.back().end < ins[i].start) res.push_back(ins[i]);
 8         else
 9             res.back().end = max(res.back().end, ins[i].end);
10     }
11     return res;
12 }

Python

https://discuss.leetcode.com/topic/17178/7-lines-easy-python

1 def merge(self, intervals):
2     out = []
3     for i in sorted(intervals, key=lambda i: i.start):
4         if out and i.start <= out[-1].end:
5             out[-1].end = max(out[-1].end, i.end)
6         else:
7             out += i,
8     return out