Is Remove Covered Intervals easy or hard?

Remove Covered Intervals is rated Medium difficulty. The coverage condition is simple, but recognizing that sorting by start and end order allows a single linear scan requires familiarity with interval and greedy patterns.

Remove Covered Intervals Python/Java solution

In Python or Java, implement a custom sort that orders intervals by start ascending and end descending. After sorting, iterate through the intervals while maintaining a variable for the largest end encountered and count intervals that are not covered.

How to solve Remove Covered Intervals in O(n)?

Pure O(n) time is generally not possible because intervals must be ordered to detect coverage efficiently. Sorting by start ascending and end descending reduces the problem to a single linear scan after sorting. The total complexity becomes O(n log n).

What is the best approach for Remove Covered Intervals?

The best approach sorts intervals by start ascending and end descending, then scans once while tracking the maximum end seen so far. If the current interval's end is less than or equal to the maximum end, it is covered. This method runs in O(n log n) time due to sorting and uses O(1) extra space.

Is Remove Covered Intervals asked at Google/Amazon/Meta?

Interval and sorting problems like Remove Covered Intervals frequently appear in interviews at companies such as Google, Amazon, and Meta. They test understanding of interval ordering, greedy scanning, and how sorting can eliminate unnecessary comparisons.

What data structure is used in Remove Covered Intervals?

The problem mainly uses arrays and sorting. Intervals are stored in an array, sorted by custom comparator rules, and then scanned while tracking the maximum end value seen so far.

What is the time complexity of Remove Covered Intervals?

The optimal solution runs in O(n log n) time because the intervals must be sorted first. After sorting, a single linear scan checks whether each interval is covered by comparing end values. The brute-force comparison approach takes O(n²) time.

Description Hints 2 Solution Video 11:56

1288. Remove Covered Intervals

Medium60.1% acceptance5 companies

Given an array intervals where intervals[i] = [l_i, r_i] represent the interval [l_i, r_i), remove all intervals that are covered by another interval in the list.

The interval [a, b) is covered by the interval [c, d) if and only if c <= a and b <= d.

Return the number of remaining intervals.

Example 1:

Input: intervals = [[1,4],[3,6],[2,8]]
Output: 2
Explanation: Interval [3,6] is covered by [2,8], therefore it is removed.

Example 2:

Input: intervals = [[1,4],[2,3]]
Output: 1

Constraints:

1 <= intervals.length <= 1000
intervals[i].length == 2
0 <= l_i < r_i <= 10⁵
All the given intervals are unique.

Asked at 5 companies

Amazon Microsoft

Google Bloomberg Meta

Topics

Array Sorting

Hints open one at a time

Hint 1

How to check if an interval is covered by another?

Hint 2

Compare each interval to all others and check if it is covered by any interval.

11:56

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def removeCoveredIntervals(self, intervals: List[List[int]]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[[1,4],[3,6],[2,8]]

Input

[[1,4],[2,3]]

Your code is saved on this device.Solution