CONY的世界

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

這題用到的概念，一個是用Collections.sort() 去排序 Interval List 內的物件 

所以這裡需要實作 Interval 的 comparator ，所以要 implements Comparator<Interval> 在這邊

因為class 已經被implement 好了，所以無法跟class implement 在一起 

所以用另立一個class 去implements Comparator<Interval>

當然要實作 int compare(T a, T b) function

相關文件：https://openhome.cc/Gossip/Java/ComparableComparator.html

然後依照Interval.start 物件排序好後一個一個取出來，然後判定是否與目前紀錄的範圍重複，如果重複就可以合併

沒有重複就直接塞到result list 

/**
 * 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 {
    class sortByStart implements Comparator<Interval>{
        public int compare(Interval a, Interval b){
            return a.start-b.start;
        }    
    }
    public List<Interval> merge(List<Interval> intervals) {
        
        Collections.sort(intervals, new sortByStart());
        List<Interval> result = new ArrayList();
        
        int start=-1, end=-1;
        intervals.add(new Interval(Integer.MAX_VALUE,Integer.MAX_VALUE));
        while(intervals.size() > 0){
            Interval cur = intervals.remove(0);
            if(start<0 || end < 0) {  
                start = cur.start; end = cur.end;
            } else if(cur.start > end) {
                result.add(new Interval(start,end));
                start = cur.start; end = cur.end;
            } else
                end = Math.max(end,cur.end);
        }
        return result;
    }
}

同樣概念，別人比較漂亮的寫法

public List<Interval> merge(List<Interval> intervals) {
    if (intervals.size() <= 1)
        return intervals;
    
    // Sort by ascending starting point using an anonymous Comparator
    intervals.sort((i1, i2) -> Integer.compare(i1.start, i2.start));
    
    List<Interval> result = new LinkedList<Interval>();
    int start = intervals.get(0).start;
    int end = intervals.get(0).end;
    
    for (Interval interval : intervals) {
        if (interval.start <= end) // Overlapping intervals, move the end if needed
            end = Math.max(end, interval.end);
        else {                     // Disjoint intervals, add the previous one and reset bounds
            result.add(new Interval(start, end));
            start = interval.start;
            end = interval.end;
        }
    }
    
    // Add the last interval
    result.add(new Interval(start, end));
    return result;
}