Remove Covered Intervals

Remove Covered Intervals

What is this problem about?

The Remove Covered Intervals interview question gives you a list of intervals, and asks you to count how many intervals remain after removing all intervals that are completely covered by another interval in the list. An interval [a, b] is covered by [c, d] if c <= a and b <= d. The goal is to determine the number of intervals that are NOT covered by any other interval.

Why is this asked in interviews?

This interval problem is commonly asked at Meta and Amazon because it tests a candidate's ability to work with sorted intervals and apply greedy logic. It is a building block for more complex interval-related problems such as merge intervals, interval scheduling, and sweep-line algorithms. Demonstrating a clean O(n log n) solution with clear reasoning about sorting criteria shows strong algorithmic fundamentals.

Algorithmic pattern used

The pattern is sorting plus greedy with a running maximum. Sort intervals by their start point in ascending order; for ties in start, sort by end in descending order. Then iterate through the sorted list, maintaining the maximum right endpoint seen so far (max_end). If the current interval's right endpoint is less than or equal to max_end, it is covered. Otherwise, update max_end and increment the answer counter.

Example explanation

Given intervals: [[1,4],[3,6],[2,8]]

Sort by start ascending, end descending: [[1,4],[2,8],[3,6]].

• [1,4]: max_end is 0 → not covered → count = 1, max_end = 4.
• [2,8]: 8 > 4 → not covered → count = 2, max_end = 8.
• [3,6]: 6 ≤ 8 → covered → skip.

Result: 2 intervals remain.

Common mistakes candidates make

• Sorting only by start without a secondary sort on end, causing incorrect coverage detection for intervals with identical start points.
• Checking both endpoints for coverage incorrectly — only the right endpoint matters once sorting is applied.
• Using an O(n^2) brute-force nested loop approach when O(n log n) is expected.
• Confusing "strictly covered" vs "partially overlapping" — only completely contained intervals should be removed.

Interview preparation tip

For the Remove Covered Intervals coding problem, practice the sorting criterion carefully: ascending start, descending end. Walking through a small example before coding will help you verify your sort order. Interviewers at Meta and Amazon look for candidates who can justify why the secondary sort on end descending is necessary — being able to explain this clearly demonstrates depth of understanding of the array and sorting interview pattern.