1288. Remove Covered Intervals - Explanation

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - Sorting arrays with custom comparators (by start time, then by end time)
Interval Problems - Understanding interval containment and overlap concepts
Greedy Algorithms - Processing intervals in sorted order to make optimal decisions

1. Brute Force

Intuition

An interval is "covered" if another interval completely contains it. We check every pair of intervals to see if one covers the other. For interval i to be covered by interval j, we need j's start to be at or before i's start, and j's end to be at or after i's end. We count how many intervals are not covered by any other.

Algorithm

Start with the total count of intervals.
For each interval i, check all other intervals j.
If interval j covers interval i (starts earlier or equal, ends later or equal), decrement the count and move to the next interval.
Return the remaining count of uncovered intervals.

Time Complexity: O(n^2) because we check each pair of intervals.

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        n = len(intervals)
        res = n

        for i in range(n):
            for j in range(n):
                if (i != j and intervals[j][0] <= intervals[i][0] and
                    intervals[j][1] >= intervals[i][1]
                ):
                    res -= 1
                    break

        return res

public class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        int n = intervals.length;
        int res = n;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && intervals[j][0] <= intervals[i][0] &&
                    intervals[j][1] >= intervals[i][1]) {
                    res--;
                    break;
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();
        int res = n;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && intervals[j][0] <= intervals[i][0] &&
                    intervals[j][1] >= intervals[i][1]) {
                    res--;
                    break;
                }
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[][]} intervals
     * @return {number}
     */
    removeCoveredIntervals(intervals) {
        let n = intervals.length;
        let res = n;

        for (let i = 0; i < n; i++) {
            for (let j = 0; j < n; j++) {
                if (
                    i !== j &&
                    intervals[j][0] <= intervals[i][0] &&
                    intervals[j][1] >= intervals[i][1]
                ) {
                    res--;
                    break;
                }
            }
        }
        return res;
    }
}

public class Solution {
    public int RemoveCoveredIntervals(int[][] intervals) {
        int n = intervals.Length;
        int res = n;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j && intervals[j][0] <= intervals[i][0] &&
                    intervals[j][1] >= intervals[i][1]) {
                    res--;
                    break;
                }
            }
        }
        return res;
    }
}

func removeCoveredIntervals(intervals [][]int) int {
    n := len(intervals)
    res := n

    for i := 0; i < n; i++ {
        for j := 0; j < n; j++ {
            if i != j && intervals[j][0] <= intervals[i][0] &&
                intervals[j][1] >= intervals[i][1] {
                res--
                break
            }
        }
    }
    return res
}

class Solution {
    fun removeCoveredIntervals(intervals: Array<IntArray>): Int {
        val n = intervals.size
        var res = n

        for (i in 0 until n) {
            for (j in 0 until n) {
                if (i != j && intervals[j][0] <= intervals[i][0] &&
                    intervals[j][1] >= intervals[i][1]) {
                    res--
                    break
                }
            }
        }
        return res
    }
}

class Solution {
    func removeCoveredIntervals(_ intervals: [[Int]]) -> Int {
        let n = intervals.count
        var res = n

        for i in 0..<n {
            for j in 0..<n {
                if i != j && intervals[j][0] <= intervals[i][0] &&
                    intervals[j][1] >= intervals[i][1] {
                    res -= 1
                    break
                }
            }
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 2)$
Space complexity: $O(1)$ extra space.

2. Sorting - I

Intuition

Sorting helps us process intervals in an order where we can easily detect covered intervals. By sorting by start time (ascending) and then by end time (descending), intervals that share the same start will have the longest one first. This means when we encounter a new interval, we only need to check if it's covered by the most recent "dominant" interval we've seen.

Algorithm

Sort intervals by start time ascending, and by end time descending for ties.
Track the previous interval's boundaries.
For each interval, if it's completely contained within the previous interval's boundaries, skip it.
Otherwise, count it as uncovered and update the tracked boundaries.
Return the count of uncovered intervals.

This sorting strategy ensures that once we sort, we only need to track prevL and prevR.

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort(key=lambda x: (x[0], -x[1]))
        res = 1
        prevL, prevR = intervals[0][0], intervals[0][1]
        for l, r in intervals:
            if prevL <= l and prevR >= r:
                continue
            res += 1
            prevL, prevR = l, r

        return res

public class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) ->
            a[0] == b[0] ? Integer.compare(b[1], a[1]) : Integer.compare(a[0], b[0])
        );
        int res = 1, prevL = intervals[0][0], prevR = intervals[0][1];
        for (int[] interval : intervals) {
            int l = interval[0], r = interval[1];
            if (prevL <= l && prevR >= r) {
                continue;
            }
            res++;
            prevL = l;
            prevR = r;
        }
        return res;
    }
}

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
            return a[0] == b[0] ? b[1] < a[1] : a[0] < b[0];
        });

        int res = 1, prevL = intervals[0][0], prevR = intervals[0][1];
        for (const auto& interval : intervals) {
            int l = interval[0], r = interval[1];
            if (prevL <= l && prevR >= r) {
                continue;
            }
            res++;
            prevL = l;
            prevR = r;
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[][]} intervals
     * @return {number}
     */
    removeCoveredIntervals(intervals) {
        intervals.sort((a, b) => (a[0] === b[0] ? b[1] - a[1] : a[0] - b[0]));
        let res = 1,
            [prevL, prevR] = intervals[0];
        for (const [l, r] of intervals) {
            if (prevL <= l && prevR >= r) {
                continue;
            }
            res++;
            prevL = l;
            prevR = r;
        }
        return res;
    }
}

public class Solution {
    public int RemoveCoveredIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) =>
            a[0] == b[0] ? b[1].CompareTo(a[1]) : a[0].CompareTo(b[0])
        );
        int res = 1, prevL = intervals[0][0], prevR = intervals[0][1];
        foreach (var interval in intervals) {
            int l = interval[0], r = interval[1];
            if (prevL <= l && prevR >= r) {
                continue;
            }
            res++;
            prevL = l;
            prevR = r;
        }
        return res;
    }
}

func removeCoveredIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        if intervals[i][0] == intervals[j][0] {
            return intervals[i][1] > intervals[j][1]
        }
        return intervals[i][0] < intervals[j][0]
    })

    res := 1
    prevL, prevR := intervals[0][0], intervals[0][1]
    for _, interval := range intervals {
        l, r := interval[0], interval[1]
        if prevL <= l && prevR >= r {
            continue
        }
        res++
        prevL, prevR = l, r
    }
    return res
}

class Solution {
    fun removeCoveredIntervals(intervals: Array<IntArray>): Int {
        intervals.sortWith(compareBy({ it[0] }, { -it[1] }))
        var res = 1
        var prevL = intervals[0][0]
        var prevR = intervals[0][1]
        for ((l, r) in intervals) {
            if (prevL <= l && prevR >= r) {
                continue
            }
            res++
            prevL = l
            prevR = r
        }
        return res
    }
}

class Solution {
    func removeCoveredIntervals(_ intervals: [[Int]]) -> Int {
        var intervals = intervals.sorted {
            $0[0] == $1[0] ? $0[1] > $1[1] : $0[0] < $1[0]
        }
        var res = 1
        var prevL = intervals[0][0], prevR = intervals[0][1]
        for interval in intervals {
            let l = interval[0], r = interval[1]
            if prevL <= l && prevR >= r {
                continue
            }
            res += 1
            prevL = l
            prevR = r
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n\log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

3. Sorting - II

Intuition

With a simpler sort by start time only, we track the maximum end point seen so far. An interval is covered if both its start is greater than or equal to a previous start AND its end is within the maximum end we've tracked. By keeping the maximum end updated, we efficiently determine coverage in a single pass.

Algorithm

Sort intervals by start time.
Track the start and maximum end of the current "dominant" interval.
For each interval, check if it extends beyond the current coverage (new start strictly greater AND new end strictly greater).
If so, it's a new uncovered interval. Update the tracked start and increment the count.
Always update the maximum end seen.
Return the count.

This approach avoids the need for special sorting by end time in reverse.

class Solution:
    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
        intervals.sort()
        res, start, end = 1, intervals[0][0], intervals[0][1]

        for l, r in intervals:
            if start < l and end < r:
                start = l
                res += 1
            end = max(end, r)

        return res

public class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
        int res = 1, start = intervals[0][0], end = intervals[0][1];

        for (int[] interval : intervals) {
            int l = interval[0], r = interval[1];
            if (start < l && end < r) {
                start = l;
                res++;
            }
            end = Math.max(end, r);
        }
        return res;
    }
}

class Solution {
public:
    int removeCoveredIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end());
        int res = 1, start = intervals[0][0], end = intervals[0][1];

        for (const auto& interval : intervals) {
            int l = interval[0], r = interval[1];
            if (start < l && end < r) {
                start = l;
                res++;
            }
            end = max(end, r);
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[][]} intervals
     * @return {number}
     */
    removeCoveredIntervals(intervals) {
        intervals.sort((a, b) => a[0] - b[0]);
        let res = 1,
            start = intervals[0][0],
            end = intervals[0][1];

        for (const [l, r] of intervals) {
            if (start < l && end < r) {
                start = l;
                res++;
            }
            end = Math.max(end, r);
        }
        return res;
    }
}

public class Solution {
    public int RemoveCoveredIntervals(int[][] intervals) {
        Array.Sort(intervals, (a, b) => a[0].CompareTo(b[0]));
        int res = 1, start = intervals[0][0], end = intervals[0][1];

        foreach (var interval in intervals) {
            int l = interval[0], r = interval[1];
            if (start < l && end < r) {
                start = l;
                res++;
            }
            end = Math.Max(end, r);
        }
        return res;
    }
}

func removeCoveredIntervals(intervals [][]int) int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]
    })

    res := 1
    start, end := intervals[0][0], intervals[0][1]
    for _, interval := range intervals {
        l, r := interval[0], interval[1]
        if start < l && end < r {
            start = l
            res++
        }
        if r > end {
            end = r
        }
    }
    return res
}

class Solution {
    fun removeCoveredIntervals(intervals: Array<IntArray>): Int {
        intervals.sortBy { it[0] }
        var res = 1
        var start = intervals[0][0]
        var end = intervals[0][1]

        for ((l, r) in intervals) {
            if (start < l && end < r) {
                start = l
                res++
            }
            end = maxOf(end, r)
        }
        return res
    }
}

class Solution {
    func removeCoveredIntervals(_ intervals: [[Int]]) -> Int {
        var intervals = intervals.sorted { $0[0] < $1[0] }
        var res = 1
        var start = intervals[0][0], end = intervals[0][1]

        for interval in intervals {
            let l = interval[0], r = interval[1]
            if start < l && end < r {
                start = l
                res += 1
            }
            end = max(end, r)
        }
        return res
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

Common Pitfalls

Incorrect Sorting Order

The most common mistake is sorting only by start time without considering the end time. When two intervals share the same start, the longer one should come first (sort by end time descending). Otherwise, you might incorrectly count the longer interval as covered by the shorter one. For example, [1,4] and [1,2] with the same start: if [1,2] comes first, you'd miss that [1,2] is covered by [1,4].

Confusing Covered vs Overlapping

An interval is covered only if another interval completely contains it (start <= start AND end >= end). Some solutions incorrectly check for overlap instead of complete containment. For [1,4] to cover [2,3], we need 1 <= 2 AND 4 >= 3. Partial overlaps like [1,3] and [2,4] don't count as one covering the other.

Off-by-One in Return Value

The problem asks for the count of intervals remaining after removal, not the count of covered intervals. Some solutions return the number of covered intervals instead of subtracting from the total. If you find k covered intervals out of n total, return n - k, not k.