Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogle

Remove Covered Intervals

Choose your preparation mode4 modes available
🎯
Remove Covered Intervals
mediumINTERVALSAmazonGoogle

Imagine you have a list of time slots booked for meetings, but some meetings are completely contained within others. You want to remove the redundant smaller meetings to simplify your schedule.

💡 This problem deals with intervals and understanding how one interval can be completely covered by another. Beginners often struggle because it requires careful sorting and comparison of intervals, not just checking for overlaps but full containment.
📋
Problem Statement

Given a list of intervals where each interval is represented as [start, end], remove all intervals that are covered by another interval in the list. An interval [a, b) is covered by an interval [c, d) if and only if c ≤ a and b ≤ d. Return the number of remaining intervals after removing the covered ones.

1 ≤ intervals.length ≤ 10^50 ≤ intervals[i][0] < intervals[i][1] ≤ 10^9
💡
Example
Input"[[1,4],[3,6],[2,8]]"
Output2

Interval [3,6] is covered by [2,8], so it is removed. Remaining intervals are [1,4] and [2,8].

  • All intervals are identical → only one remains
  • Intervals with no coverage at all → all remain
  • Intervals sorted in descending order → still works correctly
  • Intervals with large ranges and small intervals inside → small intervals removed
⚠️
Common Mistakes
Sorting intervals only by start ascending

Fails to detect coverage when intervals have same start but different ends

✅ Sort by start ascending and end descending

Checking coverage with strict inequality instead of ≤

Misses intervals that are exactly covered

✅ Use ≤ for start and end comparisons

Not updating max_end correctly

Incorrectly counts covered intervals as uncovered

✅ Update max_end only when current interval end is greater

Using nested loops for large inputs

Time limit exceeded (TLE)

✅ Use sorting + single pass approach

🧠
Brute Force (Nested Loops Checking Coverage)
💡 This approach exists to build intuition by directly checking every pair of intervals for coverage, which helps understand the problem deeply before optimizing.

Intuition

Check every interval against every other interval to see if it is covered. If yes, mark it for removal.

Algorithm

  1. Initialize a count of intervals to keep.
  2. For each interval, compare it with every other interval.
  3. If the current interval is covered by any other, mark it as covered.
  4. Return the count of intervals not marked as covered.
💡 The nested loops make it hard to see efficiency, but this approach guarantees correctness by exhaustive checking.
</>
Code
from typing import List

def remove_covered_intervals(intervals: List[List[int]]) -> int:
    n = len(intervals)
    covered = [False] * n
    for i in range(n):
        for j in range(n):
            if i != j:
                if intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]:
                    covered[i] = True
                    break
    return sum(not c for c in covered)

# Driver code
if __name__ == '__main__':
    intervals = [[1,4],[3,6],[2,8]]
    print(remove_covered_intervals(intervals))  # Output: 2
Line Notes
covered = [False] * nInitialize a boolean list to track which intervals are covered
for i in range(n)Outer loop picks the interval to check coverage for
for j in range(n)Inner loop compares with every other interval
if intervals[j][0] <= intervals[i][0] and intervals[i][1] <= intervals[j][1]Check if interval i is covered by interval j
import java.util.*;

public class RemoveCoveredIntervals {
    public static int removeCoveredIntervals(int[][] intervals) {
        int n = intervals.length;
        boolean[] covered = new boolean[n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1]) {
                        covered[i] = true;
                        break;
                    }
                }
            }
        }
        int count = 0;
        for (boolean c : covered) if (!c) count++;
        return count;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{3,6},{2,8}};
        System.out.println(removeCoveredIntervals(intervals)); // Output: 2
    }
}
Line Notes
boolean[] covered = new boolean[n];Track which intervals are covered
for (int i = 0; i < n; i++)Select interval to check
if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1])Check coverage condition
break;Stop checking once covered is confirmed
#include <iostream>
#include <vector>
using namespace std;

int removeCoveredIntervals(vector<vector<int>>& intervals) {
    int n = intervals.size();
    vector<bool> covered(n, false);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1]) {
                    covered[i] = true;
                    break;
                }
            }
        }
    }
    int count = 0;
    for (bool c : covered) if (!c) count++;
    return count;
}

int main() {
    vector<vector<int>> intervals = {{1,4},{3,6},{2,8}};
    cout << removeCoveredIntervals(intervals) << endl; // Output: 2
    return 0;
}
Line Notes
vector<bool> covered(n, false);Boolean vector to mark covered intervals
for (int i = 0; i < n; i++)Outer loop selects interval to check
if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1])Check if interval i is covered by j
break;Stop inner loop early if covered
function removeCoveredIntervals(intervals) {
    const n = intervals.length;
    const covered = new Array(n).fill(false);
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < n; j++) {
            if (i !== j) {
                if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1]) {
                    covered[i] = true;
                    break;
                }
            }
        }
    }
    return covered.filter(c => !c).length;
}

// Driver code
const intervals = [[1,4],[3,6],[2,8]];
console.log(removeCoveredIntervals(intervals)); // Output: 2
Line Notes
const covered = new Array(n).fill(false);Initialize coverage tracking array
for (let i = 0; i < n; i++)Outer loop picks interval to check
if (intervals[j][0] <= intervals[i][0] && intervals[i][1] <= intervals[j][1])Check coverage condition
break;Stop checking once coverage is found
⏱
Complexity
TimeO(n^2)
SpaceO(n)

Two nested loops each run n times, so O(n^2). The covered array uses O(n) space.

💡 For n=20, this means about 400 comparisons, which is manageable but grows quickly for large n.
Interview Verdict: TLE for large inputs

This approach is too slow for large inputs but is useful to understand the problem and correctness before optimizing.

🧠
Sorting + Single Pass Coverage Check
💡 Sorting intervals by start ascending and end descending helps us identify coverage in one pass, improving efficiency drastically.

Intuition

Sort intervals so that if one interval covers another, it appears before it. Then track the maximum end seen so far to detect coverage.

Algorithm

  1. Sort intervals by start ascending, and if tie, by end descending.
  2. Initialize max_end to 0 and count to 0.
  3. Iterate through intervals; if current interval's end is less or equal to max_end, it is covered.
  4. Otherwise, update max_end and increment count.
  5. Return count.
💡 Sorting ensures covered intervals come after their covering intervals, so a single max_end variable suffices to detect coverage.
</>
Code
from typing import List

def remove_covered_intervals(intervals: List[List[int]]) -> int:
    intervals.sort(key=lambda x: (x[0], -x[1]))
    count = 0
    max_end = 0
    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end
    return count

# Driver code
if __name__ == '__main__':
    intervals = [[1,4],[3,6],[2,8]]
    print(remove_covered_intervals(intervals))  # Output: 2
Line Notes
intervals.sort(key=lambda x: (x[0], -x[1]))Sort by start ascending, end descending to ensure coverage order
count = 0Initialize count of non-covered intervals
if end > max_endIf current interval extends beyond max_end, it is not covered
max_end = endUpdate max_end to current interval's end
import java.util.*;

public class RemoveCoveredIntervals {
    public static int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        int count = 0, maxEnd = 0;
        for (int[] interval : intervals) {
            if (interval[1] > maxEnd) {
                count++;
                maxEnd = interval[1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{3,6},{2,8}};
        System.out.println(removeCoveredIntervals(intervals)); // Output: 2
    }
}
Line Notes
Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);Sort intervals by start ascending, end descending
int count = 0, maxEnd = 0;Initialize count and maxEnd
if (interval[1] > maxEnd)Check if interval is not covered
maxEnd = interval[1];Update maxEnd to current interval's end
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int removeCoveredIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        if (a[0] != b[0]) return a[0] < b[0];
        return a[1] > b[1];
    });
    int count = 0, maxEnd = 0;
    for (auto& interval : intervals) {
        if (interval[1] > maxEnd) {
            count++;
            maxEnd = interval[1];
        }
    }
    return count;
}

int main() {
    vector<vector<int>> intervals = {{1,4},{3,6},{2,8}};
    cout << removeCoveredIntervals(intervals) << endl; // Output: 2
    return 0;
}
Line Notes
sort(intervals.begin(), intervals.end(), ...Sort intervals by start ascending, end descending
int count = 0, maxEnd = 0;Initialize count and maxEnd
if (interval[1] > maxEnd)Check if current interval is not covered
maxEnd = interval[1];Update maxEnd to current interval's end
function removeCoveredIntervals(intervals) {
    intervals.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
    let count = 0, maxEnd = 0;
    for (const [, end] of intervals) {
        if (end > maxEnd) {
            count++;
            maxEnd = end;
        }
    }
    return count;
}

// Driver code
const intervals = [[1,4],[3,6],[2,8]];
console.log(removeCoveredIntervals(intervals)); // Output: 2
Line Notes
intervals.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);Sort intervals by start ascending, end descending
let count = 0, maxEnd = 0;Initialize count and maxEnd
if (end > maxEnd)Check if current interval is not covered
maxEnd = end;Update maxEnd to current interval's end
⏱
Complexity
TimeO(n log n)
SpaceO(log n) or O(n) depending on sorting implementation

Sorting takes O(n log n), single pass is O(n). Space depends on sorting algorithm.

💡 For n=100000, sorting is efficient enough to run quickly in practice.
Interview Verdict: Accepted

This approach is efficient and accepted for large inputs, making it the preferred solution in interviews.

🧠
Sorting + In-place Counting (Space Optimized)
💡 This approach optimizes space by avoiding extra arrays and counting intervals in-place after sorting.

Intuition

After sorting, we only track max_end and count intervals that extend beyond it, no extra arrays needed.

Algorithm

  1. Sort intervals by start ascending and end descending.
  2. Initialize max_end and count to zero.
  3. Iterate intervals; if current end > max_end, increment count and update max_end.
  4. Return count.
💡 This is a streamlined version of the previous approach, focusing on minimal memory usage.
</>
Code
def remove_covered_intervals(intervals):
    intervals.sort(key=lambda x: (x[0], -x[1]))
    count = 0
    max_end = 0
    for _, end in intervals:
        if end > max_end:
            count += 1
            max_end = end
    return count

# Driver code
if __name__ == '__main__':
    intervals = [[1,4],[3,6],[2,8]]
    print(remove_covered_intervals(intervals))  # Output: 2
Line Notes
intervals.sort(key=lambda x: (x[0], -x[1]))Sort intervals to ensure coverage order
count = 0Initialize count of non-covered intervals
if end > max_endDetect if current interval is not covered
max_end = endUpdate max_end to current interval's end
import java.util.*;

public class RemoveCoveredIntervals {
    public static int removeCoveredIntervals(int[][] intervals) {
        Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);
        int count = 0, maxEnd = 0;
        for (int[] interval : intervals) {
            if (interval[1] > maxEnd) {
                count++;
                maxEnd = interval[1];
            }
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] intervals = {{1,4},{3,6},{2,8}};
        System.out.println(removeCoveredIntervals(intervals)); // Output: 2
    }
}
Line Notes
Arrays.sort(intervals, (a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);Sort intervals by start ascending, end descending
int count = 0, maxEnd = 0;Initialize count and maxEnd
if (interval[1] > maxEnd)Check if interval is not covered
maxEnd = interval[1];Update maxEnd to current interval's end
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int removeCoveredIntervals(vector<vector<int>>& intervals) {
    sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) {
        if (a[0] != b[0]) return a[0] < b[0];
        return a[1] > b[1];
    });
    int count = 0, maxEnd = 0;
    for (auto& interval : intervals) {
        if (interval[1] > maxEnd) {
            count++;
            maxEnd = interval[1];
        }
    }
    return count;
}

int main() {
    vector<vector<int>> intervals = {{1,4},{3,6},{2,8}};
    cout << removeCoveredIntervals(intervals) << endl; // Output: 2
    return 0;
}
Line Notes
sort(intervals.begin(), intervals.end(), ...Sort intervals by start ascending, end descending
int count = 0, maxEnd = 0;Initialize count and maxEnd
if (interval[1] > maxEnd)Check if current interval is not covered
maxEnd = interval[1];Update maxEnd to current interval's end
function removeCoveredIntervals(intervals) {
    intervals.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);
    let count = 0, maxEnd = 0;
    for (const [, end] of intervals) {
        if (end > maxEnd) {
            count++;
            maxEnd = end;
        }
    }
    return count;
}

// Driver code
const intervals = [[1,4],[3,6],[2,8]];
console.log(removeCoveredIntervals(intervals)); // Output: 2
Line Notes
intervals.sort((a, b) => a[0] !== b[0] ? a[0] - b[0] : b[1] - a[1]);Sort intervals by start ascending, end descending
let count = 0, maxEnd = 0;Initialize count and maxEnd
if (end > maxEnd)Check if current interval is not covered
maxEnd = end;Update maxEnd to current interval's end
⏱
Complexity
TimeO(n log n)
SpaceO(1) additional space besides input

Sorting dominates time complexity; counting is O(n). No extra arrays used.

💡 This approach is ideal when memory is constrained but sorting is allowed.
Interview Verdict: Accepted

This is the most space-efficient accepted solution, suitable for memory-sensitive environments.

📊
All Approaches - One-Glance Tradeoffs
💡 In interviews, always code the sorting + single pass approach unless asked otherwise.
ApproachTimeSpaceStack RiskReconstructUse In Interview
1. Brute ForceO(n^2)O(n)NoN/AMention only - never code due to inefficiency
2. Sorting + Single PassO(n log n)O(n) or O(log n) due to sortingNoN/ACode this as optimal solution
3. Sorting + In-place CountingO(n log n)O(1) additionalNoN/AMention as space optimized variant
💼
Interview Strategy
💡 Use this guide to understand the problem deeply, practice coding all approaches, and prepare to explain tradeoffs clearly in interviews.

How to Present

Step 1: Clarify the problem and constraints with the interviewer.Step 2: Present the brute force approach to show understanding.Step 3: Discuss inefficiencies and propose sorting-based optimization.Step 4: Code the optimal approach with sorting and single pass.Step 5: Test with examples and edge cases.

Time Allocation

Clarify: 2min → Approach: 5min → Code: 10min → Test: 3min. Total ~20min

What the Interviewer Tests

The interviewer tests your ability to recognize interval coverage, optimize with sorting, and write clean, efficient code.

Common Follow-ups

  • What if intervals are not sorted? → Sorting is necessary for efficient solution.
  • Can you do it without sorting? → Brute force only, inefficient for large inputs.
  • How to handle intervals with same start and end? → Sort by end descending to handle coverage correctly.
  • What if intervals are very large? → Sorting still works efficiently.
💡 These follow-ups test your understanding of sorting importance, edge cases, and scalability.
🔍
Pattern Recognition

When to Use

1) Problem involves intervals, 2) Need to remove or count intervals covered by others, 3) Coverage defined by start and end containment, 4) Sorting can simplify comparisons.

Signature Phrases

remove intervals covered by anotherinterval [a,b) is covered if c ≤ a and b ≤ d

NOT This Pattern When

Problems that only require detecting overlaps without coverage, or interval scheduling problems.

Similar Problems

Merge Intervals - merging overlapping intervals to simplify interval setsInsert Interval - inserting and merging intervals maintaining orderNon-overlapping Intervals - removing minimum intervals to avoid overlap

Practice

(1/5)
1. You are given a list of meeting time intervals consisting of start and end times. Your task is to find the minimum number of conference rooms required so that all meetings can be held without overlap. Which of the following approaches guarantees an optimal solution with efficient time complexity?
easy
A. Sort intervals by start time and use a min-heap to track the earliest ending meeting to reuse rooms efficiently.
B. Use a brute force approach checking every pair of intervals for overlap and counting maximum overlaps.
C. Use dynamic programming to find the maximum number of non-overlapping intervals and subtract from total intervals.
D. Sort intervals by end time and greedily assign rooms without tracking ongoing meetings.

Solution

  1. Step 1: Understand the problem requires tracking overlapping intervals to find minimum rooms.

    Brute force checks all pairs but is inefficient; greedy by end time alone doesn't track concurrent overlaps.
  2. Step 2: Recognize that sorting by start time and using a min-heap to track earliest ending meeting allows reusing rooms optimally.

    This approach efficiently manages room allocation by freeing rooms as meetings end.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Min-heap approach is standard optimal solution for this problem [OK]
Hint: Min-heap tracks earliest end to reuse rooms efficiently [OK]
Common Mistakes:
  • Assuming greedy by end time alone suffices
  • Thinking brute force is efficient enough
  • Confusing DP for interval scheduling with room allocation
2. What is the time complexity of the optimal approach that inserts a new interval into a list of n intervals and merges overlapping intervals, where the approach is to append the new interval, sort all intervals by start time, then merge in one pass?
medium
A. O(n)
B. O(n^2)
C. O(n log n)
D. O(log n)

Solution

  1. Step 1: Identify sorting cost

    Appending is O(1), but sorting n+1 intervals takes O(n log n) time.
  2. Step 2: Identify merging cost

    Merging intervals in one pass is O(n) since each interval is processed once.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sorting dominates overall time complexity [OK]
Hint: Sorting dominates time complexity -> O(n log n) [OK]
Common Mistakes:
  • Assuming linear time because merging is O(n)
  • Confusing sorting cost with merging cost
  • Thinking recursion stack adds extra complexity
3. Suppose the problem is extended so that numbers can be added multiple times (duplicates allowed), and the intervals must reflect the count of each number (e.g., intervals store counts of coverage). Which modification to the optimal balanced tree approach is necessary to handle this correctly?
hard
A. Augment intervals with counts and update counts on insertion; merge intervals only if counts allow.
B. Keep the current approach but ignore duplicates since intervals are disjoint sets.
C. Use a brute force approach storing all numbers and recomputing intervals with counts on each query.
D. Replace balanced tree with a hash map keyed by number to track counts and intervals separately.

Solution

  1. Step 1: Understand the impact of duplicates

    Intervals must now track counts, so simple presence is insufficient.
  2. Step 2: Modify data structure

    Intervals should store counts per interval or per number; merging must consider counts to avoid losing duplicates.
  3. Step 3: Evaluate options

    Ignoring duplicates (B) breaks correctness. Brute force (C) is inefficient. Hash map (D) loses interval ordering benefits. Augmenting intervals with counts (A) preserves efficiency and correctness.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Counting duplicates requires augmenting intervals [OK]
Hint: Track counts in intervals to handle duplicates correctly [OK]
Common Mistakes:
  • Ignoring duplicates
  • Using brute force for counts
  • Losing interval order with hash maps
4. Suppose balloons can be reused multiple times after bursting (i.e., an arrow can burst a balloon multiple times if shot at different points). How does this affect the algorithm to find the minimum number of arrows needed?
hard
A. The original greedy algorithm still applies without changes.
B. We must use dynamic programming to track multiple bursts per balloon.
C. The problem reduces to counting unique balloons since reuse removes overlap constraints.
D. We can shoot arrows only at balloon start points to minimize arrows.

Solution

  1. Step 1: Understand reuse effect

    If balloons can be burst multiple times independently, overlapping intervals no longer reduce arrow count.
  2. Step 2: Simplify problem

    Each balloon requires at least one arrow, so minimum arrows equal number of unique balloons.
  3. Step 3: Algorithm implication

    Overlap and interval sorting become irrelevant; counting balloons suffices.
  4. Final Answer:

    Option C -> Option C
  5. Quick Check:

    Reuse breaks overlap optimization, so count balloons directly [OK]
Hint: Reuse removes overlap benefit; count balloons directly [OK]
Common Mistakes:
  • Assuming greedy still works unchanged
  • Trying to track multiple bursts with DP unnecessarily
  • Ignoring that reuse breaks interval overlap logic
5. Suppose intervals can be reused multiple times (i.e., you can select the same interval multiple times if it does not overlap with itself). Which modification to the greedy algorithm is correct to find the maximum number of non-overlapping intervals under this new condition?
hard
A. Sort intervals by end time and greedily select intervals, resetting last_end after each selection to allow reuse.
B. Use dynamic programming to consider multiple selections of intervals, since greedy no longer works.
C. Sort intervals by start time and greedily select intervals without updating last_end to allow reuse.
D. Sort intervals by end time and greedily select intervals, but allow intervals to be selected multiple times by not updating last_end.

Solution

  1. Step 1: Understand reuse changes problem

    Allowing reuse means intervals can be selected multiple times, breaking the greedy assumption of one-time selection.
  2. Step 2: Identify correct approach

    Dynamic programming is needed to explore multiple selections and ensure maximum count without overlap.
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Greedy fails with reuse; DP handles multiple selections [OK]
Hint: Reuse breaks greedy; DP needed for multiple selections [OK]
Common Mistakes:
  • Trying to reuse intervals by resetting last_end incorrectly
  • Ignoring overlap constraints when reusing intervals
  • Assuming greedy still works unchanged
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard