56. merge intervals

 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */
class  {
    public List<Interval> merge(List<Interval> intervals) {
        int n = intervals.size();
        if (n <= 1) {
            return intervals;
        }
        int[] start = new int[n];
        int[] end = new int[n];
        int i = 0;
        for (Interval interval : intervals) {
            start[i] = interval.start;
            end[i++] = interval.end;
        }
        Arrays.sort(start);
        Arrays.sort(end);
        List<Interval> result = new ArrayList<>();
        int j = 0;
        int s = start[0];
        for (i = 1; i < n; i++, j++) {
            if (start[i] > end[j]) {
                result.add(new Interval(s, end[j]));
                s = start[i];
            }
        }
        result.add(new Interval(s, end[n-1]));
        return result;
    }
}