Merge Intervals

题目:

Given a collection of intervals, merge all overlapping intervals.

分析:

这题目其实考察的是sort Intervals的方法,在sort了之后就比较好处理了

java里面这个用callback function写comparator的方法实很有意思

解法:

class Solution {
    /**
     * @param intervals, a collection of intervals
     * @return: A new sorted interval list.
     */
    public List<Interval> merge(List<Interval> intervals) {
        // write your code here
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }

        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
            }
        });

        ArrayList<Interval> res = new ArrayList<Interval>();
        Interval prev = intervals.get(0);
        for(int i = 1; i < intervals.size(); i++) {
            Interval curr = intervals.get(i);
            if (curr.start > prev.end ) {
                res.add(prev);
                prev = curr;
            } else {
                prev.end = Math.max(prev.end, curr.end);
            }
        }

        res.add(prev);
        return res;
    }
}

results matching ""

    No results matching ""