#56 Merge Intervals

Dropbox phone interview的download chunk是從這題改的。

題目提供Interval資料結構，裡面有起始index和終止index。

input是List<Interval>，是一個List裡存了很多"區間"，其中有些區間有重疊的部分，

目標是將有重疊的區間結合成一個大區間，最後回傳List<Interval>。

做法是將所有Interval依照startIndex排序，

排序完就可以依序讀取，當current Interval的startIndex < 前一個Interval的endIndex，表示兩區間重疊，

則呼叫另一個function: merge，將兩區間結合。

另外一個做法是宣告一個boolean array(bitset)，

依序讀取Interval時就把區間包含到的所有element設為true(1)，

最後再讀取boolean array把連續1的區間輸出。

這個方法在leetcode不會過，因為leetcode要求完全重疊才要merge，接合的不可以，

例如[1,4] [5,8]不可以輸出成[1,8]，[1,5][5,8]才可以。

完整程式碼：

/**
 * 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> ans = new ArrayList<>();
        //sort intervals by start implemented by collection.sort

        Collections.sort(intervals, new Comparator<Interval>(){
            @Override
            public int compare(Interval i1, Interval i2) {
                return Integer.compare(i1.start, i2.start);
            }
        });

        //while(intervals.size()>0)
        //  cur = intervals.get(0)
        //  delete cur from intervals
        //  Interval mergeCur = merge(intervals, cur) // merge all Interval in intervals that can be merge with cur
        //  add mergeCur to ans
        while(intervals.size()>0){
            Interval cur = intervals.get(0);
            intervals.remove(0);
            Interval mergeCur = merge(intervals, cur);
            ans.add(mergeCur);
        }
        return ans;

    }
        //function: Interval merge(intervals, cur)
        //int start = cur.start 
        //int end = cur.end 
        //for each Interval in intervals
        //  if(start in Interval || end in Interval)
        //      expand cur
        //      change value of start or end
        //      delete Interval
        //  else continue
        //return Interval

        Interval merge(List<Interval> intervals, Interval cur){
            int start = cur.start;
            int end = cur.end;
            int n = intervals.size();
            for(int j=0; j<n; j++){
                Interval i = intervals.get(0);
                if( i.start <= end ){
                    start = Math.min(start, i.start);
                    end = Math.max(end, i.end);
                    intervals.remove(0);
                }
                else continue;
            }
            return new Interval(start, end);
        }
}