leetcodeマージ区間-アルゴリズム詳細解析コメント付き

区間の集合を指定します.重複するすべての区間をマージしてください.
例1:

  : [[1,3],[2,6],[8,10],[15,18]]
  : [[1,6],[8,10],[15,18]]
  :    [1,3]   [2,6]   ,        [1,6].

例2:

  : [[1,4],[4,5]]
  : [[1,5]]
  :    [1,4]   [4,5]         。

アルゴリズムの説明:
1、まずソートし、区間の開始startに基づいてソートしなければならない.Collectionsを呼び出す.sort(集合,new Comparetor{実装startをサイズ比較})実装. 
2、秩序ある区間集合があれば、各区間を巡ることができます.エンキュー対象の基準区間(最初は最初の区間)を定義し、現在遍歴している区間のstartがエンキュー対象基準区間end以下であるかどうかを比較します.もしそうなら、この2つの区間を統合して、基準区間のendを修正することができます.そうでなければ、このエンキュー対象の基準区間は、結果キューに直接追加され、エンキュー対象の基準区間が遍歴したばかりの区間に更新されます.
    

public class MergeInterval {

    public class Interval {
        int start;
        int end;

        Interval() {
            start = 0;
            end = 0;
        }

        Interval(int s, int e) {
            start = s;
            end = e;
        }
    }

    /**
     *     ，     ，             
     */
    public List merge(List intervals) {
        if (intervals == null) {
            throw new IllegalArgumentException("this intervals list is null");
        }
        if (intervals.size() <= 1) {
            return intervals;
        }
        //  
        Collections.sort(intervals, new Comparator() {
            @Override
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        //     
        List result = new LinkedList<>();
        //            start 、end，           ，               
        int start = intervals.get(0).start;
        int end = intervals.get(0).end;
        for (Interval i : intervals) {//       
            if (i.start <= end) {//       ，              
                end = Math.max(end, i.end);//   ，    ，            
            } else {//      ，                       
                result.add(new Interval(start, end));
                start = i.start;//            ，           
                end = i.end;
            }
        }
        Interval interval = new Interval(start, end);//          
        result.add(interval);
        return result;
    }
}