1288. Remove Covered Intervals

T: O(nlogn)
S: O(1)

class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        
        int prevEnd = 0;
        int res = 0;
        for (int[] interval : intervals) {
            if (interval[1] > prevEnd) { // not covered case
                res++;
                prevEnd = interval[1]; // so preEnd is the new end (not covered case, 獨立的)
            }
        }
        return res;
    }
}
/*
[[1,  4],
    [3, 6],
  [2,     8]]
  
  [[1,    4],
     [2,3]]
     
The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

1.
[[1,  4],
  [2,      8]]
     [3, 6],  -> cover: interval[1] (6) <= prevEnd (8)
 becuase sort start, so start will asc
 so covered case is => new end <= prev end 
 
 => so not covered case is: 
 when new end > prev end => do result++ and update prevEnd = new end
 
 
 2.
 but there is a edge case, when start is the same
 
 like this, => new end > prev end, res++ will fail, actually it's covered
 |----|
 |------|
 res ++ means no cover, so no merge, so add intervals, 
 in this case, fail to detect there is a cover, so res++ 
 
 so trick way is when start is same, do end sort desc
 
 => become this, so  new end > prev end  works!
 |------|
 |----|
detect there is a cover, so dont do res++ 



[[1,  4],
  [2,      8]]
     [3, 6],
       4, 5
       

Ｔ：O(nlogn)
S: O(1)
*/

new - this style also work for 2345

Ｔ：O(nlogn)
S: O(1)

```java
class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        // when start are the same, select long end first 
        // |------------|. (select long end first, for merging)
        // |----|
        Arrays.sort(intervals, (a, b) -> a[0] == b[0] ? b[1] - a[1] : a[0] - b[0]);
        int n = intervals.length;
        int count = 0;
        int i = 0;
        while (i < n) {
            int j = i+1;
            count++;
            while (j < n && intervals[i][1] >= intervals[j][1]) {
                j++;
            }
            i = j;
        }
        return count;
    }
}

/*
1     4
  2           8 
   3       6
  
*/
```

latest version:

```java
class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        // when start are the same, sort by end desc for ex: [[1,2],[1,4],[3,4]]
        Arrays.sort(intervals, (a,b) -> a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0]));
        int s = intervals[0][0];
        int e = intervals[0][1];
        int count = intervals.length;
        for (int i = 1; i < intervals.length; i++) {
            if (s <= intervals[i][0] && e >= intervals[i][1]) { // when s e can cover current interval, remove it
                count--;
            } else {
                s = intervals[i][0];
                e = intervals[i][1];
            }
        }
        return count;
    }
}


/***
T: O(nlogn)
S: O(1)

1  2
1    4
   3 4





   2    8
1    4
    3 6  


1        4
   2   3 

1                  10
    2 3
        4 5

      [ ]
   [        ]     

 */
```