package com.freetymekiyan.algorithms.level.hard;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * Given a collection of intervals, merge all overlapping intervals.
 * <p>
 * For example,
 * Given [1,3],[2,6],[8,10],[15,18],
 * return [1,6],[8,10],[15,18].
 * <p>
 * Company Tags: LinkedIn, Google, Facebook, Twitter, Microsoft, Bloomberg, Yelp
 * Tags: Array, Sort
 * Similar Problems: (H) Insert Interval, (E) Meeting Rooms, (M) Meeting Rooms II
 */
public class MergeIntervals {


    /**
     * Sort and merge, O(nlogn) time.
     * Sort the intervals according to the start value in asc order.
     * For each of the intervals,
     * 1) add to result directly if the result list is empty.
     * 2) add to result directly if there is no overlap between current interval and previous interval.
     * 3) If there is overlap, we already know current interval's start is larger than previous interval.
     * We need to update the end of previous interval if current interval's end is larger.
     */
    public List<Interval> merge(List<Interval> intervals) {
        List<Interval> res = new ArrayList<>();
        if (intervals == null || intervals.size() == 0) {
            return res;
        }
        Collections.sort(intervals, (i1, i2) -> i1.start - i2.start);
        Interval prev = null; // A pointer to the last interval in list
        for (Interval i : intervals) {
            if (prev == null || prev.end < i.start) { // Empty list or no overlap
                res.add(i);
                prev = i; // Update pointer
            } else if (i.end > prev.end) { // Overlap and the end of new interval is larger
                prev.end = i.end; // Update end
            }
        }
        return res;
    }

    /**
     * Interval class provided by leetcode.
     */
    public class Interval {

        int start;
        int end;

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

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

@@ -540,19 +540,9 @@
 Sort
- and merge,
+.
  O(n
@@ -547,17 +547,17 @@
 (nlogn) 
-t
+T
 ime.%0A   
@@ -583,49 +583,90 @@
 als 
-according to the start value in asc order
+by start time, ascending.%0A     * Use a pointer, prev, for previous merged interval
 .%0A  
@@ -699,17 +699,17 @@
 vals
-,
+:
 %0A     * 
 1) a
@@ -708,179 +708,185 @@
   * 
-1) add to result directly if the result list is empty.%0A     * 2) add to result directly if there is no overlap between current interval and previous interval.%0A     * 3) If
+%7C If prev == null, merged is empty, add directly and update prev.%0A     * %7C If prev.end %3C i.start, no overlap, add directly and update prev.%0A     * %7C Else if prev.end %3E= i.start,
  the
@@ -902,11 +902,22 @@
 rlap
-, w
+.%0A     * %7C   W
 e al
@@ -931,76 +931,148 @@
 now 
-current interval's start is larger than previous interval.%0A     * We
+i.start %3E= prev.start because of sorting. No need to update start.%0A     * %7C   Only update end is enough.%0A     * %7C   If prev.end %3E= i.end, no
  nee
@@ -1087,72 +1087,64 @@
 ate 
-the 
 end
- of previous interval if current interval's end is larger
+.%0A     * %7C   If prev.end %3C i.end, update end to i.end
 .%0A  
@@ -1213,56 +1213,8 @@
 ) %7B%0A
-        List%3CInterval%3E res = new ArrayList%3C%3E();%0A
     
@@ -1263,12 +1263,12 @@
 e() 
-== 0
+%3C= 1
 ) %7B%0A
@@ -1282,26 +1282,32 @@
      return 
-re
+interval
 s;%0A        %7D
@@ -1299,32 +1299,83 @@
 vals;%0A        %7D%0A
+        List%3CInterval%3E merged = new ArrayList%3C%3E();%0A
         Collecti
@@ -1410,16 +1410,32 @@
  -%3E 
+Integer.compare(
 i1.start
  - i
@@ -1430,18 +1430,17 @@
 i1.start
- -
+,
  i2.star
@@ -1441,16 +1441,17 @@
 2.start)
+)
 ;%0A      
@@ -1511,20 +1511,28 @@
 rval in 
+merged 
 list
+.
 %0A       
@@ -1644,16 +1644,17 @@
  overlap
+.
 %0A       
@@ -1662,19 +1662,22 @@
         
-res
+merged
 .add(i);
@@ -1713,23 +1713,33 @@
  Update 
+previous 
 pointer
+.
 %0A       
@@ -1758,20 +1758,20 @@
 if (
-i
+prev
 .end 
-%3E prev
+%3C i
 .end
@@ -1800,19 +1800,23 @@
  end of 
-new
+current
  interva
@@ -1826,16 +1826,17 @@
 s larger
+.
 %0A       
@@ -1872,19 +1872,38 @@
  Update 
-end
+previous end to merge.
 %0A       
@@ -1938,11 +1938,14 @@
 urn 
-res
+merged
 ;%0A  

update merge intervals