Practice/Google/Leetcode 1288. Remove Covered Intervals

Leetcode 1288. Remove Covered Intervals

CodingMust

Problem

You are given a collection of intervals where each interval is represented as a pair of integers [start, end]. An interval [a, b] is considered covered by another interval [c, d] if and only if c <= a and b <= d.

Your task is to remove all covered intervals from the collection and return the count of intervals that remain after removal.

Requirements

1. Identify which intervals are completely covered by other intervals
2. Count only the intervals that are not covered by any other interval
3. An interval cannot cover itself (comparing an interval to itself doesn't count)
4. Return the total count of non-covered intervals

Constraints

• 1 ≤= intervals.length ≤= 1000
• intervals[i].length == 2
• 0 ≤= intervals[i][0] < intervals[i][1] ≤= 10^5
• All intervals are valid (start < end)

Examples

Example 1:

Input: intervals = [[1,4],[3,6],[2,8]] Output: 2 Explanation: The interval [3,6] is covered by [2,8] because 2 <= 3 and 6 <= 8. After removing [3,6], we have 2 intervals remaining: [1,4] and [2,8].

Example 2:

Input: intervals = [[1,4],[2,3]] Output: 1 Explanation: The interval [2,3] is covered by [1,4] because 1 <= 2 and 3 <= 4. After removing [2,3], only 1 interval remains.

Example 3:

Input: intervals = [[1,2],[1,3],[1,4]] Output: 1 Explanation: [1,2] is covered by [1,3], and [1,3] is covered by [1,4]. Only [1,4] remains, giving us 1 interval.