Merge Intervals@LeetCode

LeetCode

Word count: 284 / Reading time: 1 min

 2015/04/07   Share

Merge Intervals

这也是一题我有点不太能理解为什么可以标为hard的题目。解法其实很直观，就是先对interval进行排序，然后遍历一遍。这里需要注意的点有两个：

对interval进行排序需要构造一个比较器。
在遍历过程中，如果结果集合为空或者当前interval与结果集合中的最后一个interval不重叠，那么就直接将当前interval直接加入到结果集合中；如果发生了重叠，那么将结果集合的最后一个interval的右端点改为当前interval的右端点。

实现代码：

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> result = new ArrayList<Interval>();
        Comparator<Interval> comparator = new Comparator<Interval>() {
            @Override
            public int compare(Interval o1, Interval o2) {
                if (o1.start == o2.start) {
                    return o1.end - o2.end;
                }
                return o1.start - o2.start;
            }
        };
        Collections.sort(intervals, comparator);
        for (Interval interval : intervals) {
            int last = result.size();
            if (last == 0 || result.get(last - 1).end < interval.start) {
                Interval newInterval = new Interval(interval.start, interval.end);
                result.add(newInterval);
            } else {
                result.get(last - 1).end = Math.max(interval.end, result.get(last - 1).end);
            }
        }
        return result;
    }
}

原文作者: findingsea

原文链接: http://findingsea.github.io/2015/04/07/merge-intervals-at-leetcode/

发表日期: April 7th 2015, 9:22:00 am

Next Post

Java 用自定义类型作为HashMap的键
Previous Post

N-Queens I II@LeetCode

CATALOG

1. Merge Intervals

