Merge Intervals

lc 56

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

排序以后，用第一个作为last interval，然后一个一个merge即可

class Solution {
    class Intervals {
        int index;
        int flag;
        public Intervals(int index, int flag) {
            this.index = index;
            this.flag = flag;
        }
    }

    class Point {
        int x;
        int y;
        public Point(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }


    public int[][] merge(int[][] intervals) {
        if (intervals == null || intervals.length == 0) return intervals;
        PriorityQueue<Intervals> queue = new PriorityQueue<Intervals>(intervals.length, new Comparator<Intervals>(){
            public int compare(Intervals a, Intervals b) {
                if (a.index == b.index) {
                    return a.flag - b.flag;
                }
                return a.index - b.index;
            }
        });
        for (int i = 0; i < intervals.length; i++) {
            queue.offer(new Intervals(intervals[i][0], 0));
            queue.offer(new Intervals(intervals[i][1], 1));
        }
        List<Point> res = new ArrayList<>();
        int count = 0;
        int start = 0;
        while (!queue.isEmpty()) {
            Intervals cur = queue.poll();
            if (cur.flag != 1) {
                count++;
                if (count == 1) {
                    start = cur.index;
                }
            } else {
                count--;
                if (count == 0) {
                    res.add(new Point(start, cur.index));
                }
            } 
        }
        int[][] result = new int[res.size()][2];

        for (int i = 0; i < res.size(); i++) {
            Point cur = res.get(i);
            result[i][0] = cur.x;
            result[i][1] = cur.y;
        }
        return result;
    }
}

/**
 * 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; }
 * }
 */
public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }

        Collections.sort(intervals, new IntervalComparator());       

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

        result.add(last);
        return result;
    }


    private class IntervalComparator implements Comparator<Interval> {
        public int compare(Interval a, Interval b) {
            return a.start - b.start;
        }
    }
}