• [x] ### PriorityQueue
• [x] ### 扫描线 最优秀
• Time O(nlogn)排序

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

并不能保证第一个元素有序

并不能保证第二个元素也有序

我用了个priority queue

/**
 * 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 Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }
        List<Interval> ans = new ArrayList<Interval>();
        PriorityQueue<Interval> queue = new PriorityQueue<>(intervals.size() , (a, b) -> (a.start - b.start));
        for (Interval inter : intervals) {
            queue.offer(inter);
        }
        Interval prev = null;
        Interval curt = null;

        while (!queue.isEmpty()) {
            if (prev == null) {
                prev = queue.poll();
                ans.add(prev);
                continue;
            }
            prev = ans.get(ans.size() - 1);
            curt = queue.poll();
            // [ 0, 5] [1 , 4]
            if (curt.start > prev.end) {
                ans.add(curt);
            }else{
                prev.end = (prev.end < curt.end) ? curt.end : prev.end;
            }
        }
        return ans;
    }
}

// //           |___|      |_____|
//                |_____|     |_______|
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals == null || intervals.size() <= 1) {
            return intervals;
        }
        List<Interval> ans = new ArrayList<Interval>();
        Collections.sort(intervals, (a,b) -> (a.start - b.start));
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval interval : intervals) {
            if (interval.start <= end) {
                end = Math.max(end, interval.end);
            }else{
                ans.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }
        ans.add(new Interval(start,end));
        return ans;
    }
}