LeetCode 56.Merge Intervals

Question

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

Explanation

主要思想是按照start来排序，然后比较end。这里可以用collections来sort，也可以用priorityqueue来存，如果用heap的话就多了一些空间。

Code

Solution 1: Heap

/**
 * 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) {
        List<Interval> result = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) return result;
        PriorityQueue<Interval> heap = new PriorityQueue<>((a,b)->(a.start - b.start));
        for(Interval interval : intervals) {
            heap.add(interval);
        }
        Interval first = heap.peek();
        int start = first.start;
        int end = first.end;
        while(!heap.isEmpty()) {
            Interval curr = heap.poll();
            int currStart = curr.start;
            int currEnd = curr.end;
            if (end >= currStart){
                if(end <= currEnd) {
                    end = currEnd;
                }
            } else {
                result.add(new Interval(start, end));
                start = currStart;
                end = currEnd;

            }

        }
        result.add(new Interval(start, end));
        return result;

    }
}

Solution 2: Collections Sort

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval>  list = new ArrayList<>();
        if (intervals==null || intervals.size()== 0) return list;
        Collections.sort(intervals,new Comparator<Interval>(){
                     public int compare(Interval s1,Interval s2){
                           return s1.start - s2.start;
                     }});
        // System.out.println(intervals.toString());
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval interval : intervals) {
            if ((interval.start) <= end) {
                if (interval.end >= end) {
                    end = interval.end;
                }
            } else {
                list.add(new Interval(start, end));
                start = interval.start;
                end = interval.end;
            }
        }

        list.add(new Interval(start, end));
        return list;

    }
}