# 1288. Remove Covered Intervals

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

```java
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
```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
```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

      [ ]
   [        ]     

 */
```
````


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/array_problem/1288.-remove-covered-intervals.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.