435. Non-overlapping Intervals

T: O(nlogn)

S: O(1)

```java
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[1] - b[1]);
        int preEnd = intervals[0][1];
        int count = 1; // at least we have one is non-overlaping
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] >= preEnd) {
                count++;
                preEnd = intervals[i][1];
            }
        }
        return intervals.length - count;
    }
}
/*
1 2
1.  3
  2 3
    3 4

1 2
1 2
1 2

|------|
|----|
    |-------|

1.              100
1     11
      11.  22
  2      12    

      end
|----| 
  |---------|  
       |--|

|----| 
       |--|   
  |---------|            
*/
```

positive one

```java
class Solution {
    public int eraseOverlapIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> Integer.compare(a[1], b[1]));

        int count = 0;
        int preEnd = intervals[0][1];
        for (int i = 1; i < intervals.length; i++) {
            if (intervals[i][0] < preEnd) {
                count++;
            } else {
                preEnd = intervals[i][1];
            }
        }
        return count;
    }
}


/*
  
case 1: 
|------------|
  |--|
        |---|

  if start < end -> remove

  if we sort by start -> remove 2!

  but for this case, actually we only need to remove one interval!

  so sort by end   


case 2:  
  |--|
        |---|   
|------------|   -> if start < end , remove 1

  |------|
        |--|   remove this one, because remain the end is more far for following intervals
|------------|


   |------|  -> make previous end samller, it's benefit for other non-overlapping intervals
|------------|



1 2
  2 3
1   3
    3. 4
*/
```