1272. Remove Interval

T: O(n)

S: O(n)

class Solution {
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<List<Integer>> res = new ArrayList<>();
        
        for (int[] interval : intervals) {
            // no overlap
            if (toBeRemoved[0] > interval[1] || interval[0] > toBeRemoved[1]) { 
                res.add(Arrays.asList(interval[0], interval[1]));
            } else {
                // overlap case  will auto be => toBeRemoved[0] < interval[1] && interval[0] < toBeRemoved[1]
                if (toBeRemoved[0] >  interval[0]) { // toBeRemoved[0] < interval[1], so it only needs compare left start
                    res.add(Arrays.asList(interval[0], toBeRemoved[0])); // left non overlap 
                }
                if (interval[1] > toBeRemoved[1]) { // interval[0] < toBeRemoved[1], so it only needs compare right end
                    res.add(Arrays.asList(toBeRemoved[1], interval[1])); // right non overlap 
                }
            }
        }
        return res;
    }
}

/*

for each intervals to compare with toBeRemoved

remain the non-overlaping part, add to res

a is interval
if b is toBeRemoved

3. these two also work in 2.
   a 
|     |        =>  [a.start, b.start)
    |   b  |
    
        a
     |    |    =>  [b.end, a.end)
|   b   |


2. 
so this is why two if, we can remove b into 2 parts
   a
|         |    =>  [a.start,b.start), [b.end, a.end)  => can treat by case 1, 2 seperaly
   |  b |


     a
   |   |
 |     b   |   => [] => no handle

 1.  
 first exclue no-overlapping case, so directly add |a|
 | a |
        |.b |  => [a]
        
          | a |
    |.b |       => [a]

*/

latest comment:

```java
class Solution {
    public List<List<Integer>> removeInterval(int[][] intervals, int[] toBeRemoved) {
        List<List<Integer>> result = new ArrayList<>();
        int rStart = toBeRemoved[0];
        int rEnd = toBeRemoved[1];
        for (int[] in : intervals) {
            int start = in[0];
            int end = in[1];
           
            /***. no overlapping (add interval)
            s. e 
            ----   rs. re
                   ----
                   s.    e
                   -----
            rs. re      
            -----
            
             */
            if (rStart > end || start > rEnd) {
                result.add(Arrays.asList(start, end));
            } else {
                /**
                overlapping (remove overlapping then add interval)
                    s             e
                     -------------
                    s-----    ---- e 
                        --------
                        rs     re
                 */
                if (rStart > start) {
                    result.add(Arrays.asList(start, rStart));
                }
                if (rEnd < end) {
                    result.add(Arrays.asList(rEnd, end));
                }

            }
        }
        return result;
    }
}


/***
use 

2 case: 

no overlapping
add inv

has overlapping
 
remove overlapping then add inv


T: O(n)
S: O(n)
 */
```