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

解题思路：排序。

Java代码：

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

class Interval {
    int start;
    int end;

    Interval() {
        start = 0;
        end = 0;
    }

    Interval(int s, int e) {
        start = s;
        end = e;
    }
}

public class Solution {
    public List merge(List intervals) {
        List result = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return result;
        }
        
        Collections.sort(intervals, new Comparator() {

            @Override
            public int compare(Interval o1, Interval o2) {
                // TODO Auto-generated method stub
                if (o1.start > o2.start) {
                    return 1;
                } else if (o1.start < o2.start) {
                    return -1;
                } else {
                    return 0;
                }
            }
        });
        result.add(intervals.get(0));
        for (Interval interval : intervals) {
            Interval lastOne = result.get(result.size() - 1);
            if (interval.start <= lastOne.end) {
                lastOne.end = Math.max(interval.end, lastOne.end);
            } else {
                result.add(interval);
            }
        }
        return result;
    }
}