Remove Covered Intervals

🎯

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.

Approach	Time	Space	Stack Risk	Reconstruct	Use In Interview
1. Brute Force	O(n^2)	O(n)	No	N/A	Mention only - never code due to inefficiency
2. Sorting + Single Pass	O(n log n)	O(n) or O(log n) due to sorting	No	N/A	Code this as optimal solution
3. Sorting + In-place Counting	O(n log n)	O(1) additional	No	N/A	Mention 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. Consider the following Python function implementing the line sweep algorithm to count intervals containing each point. Given intervals = [[1,4],[2,5],[7,9]] and points = [2,5,8], what is the final output of the function call count_intervals_line_sweep(intervals, points)?

easy

A. [2, 1, 1]

B. [2, 1, 0]

C. [1, 2, 1]

D. [2, 2, 1]

Solution

1. Step 1: Sort events and process starts

   Events: (1,+1), (2,+1), (2,0), (5,0), (5+1,-1), (4+1,-1), (7,+1), (8,0), (9+1,-1). Sorted order processes starts before points, points before ends.

2. Step 2: Track active intervals and assign counts at points

   At point 2: active=2 (intervals [1,4],[2,5]), at point 5: active=1 (only [2,5] ends at 6), at point 8: active=0 (interval [7,9] ended at 10, but 8 < 10 so active=1 actually, re-check)

3. Correction Step 2:

   At point 8: interval [7,9] is active, so active=1. So final counts: [2,1,1]

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Counting active intervals at each point matches expected output [OK]

Hint: Remember to add 1 to interval ends for event ordering [OK]

Common Mistakes:

• Forgetting end+1 shifts interval end
• Misordering events causing wrong active count
• Off-by-one in active count at points

2. The following code attempts to add a number to the intervals but contains a subtle bug. Which line causes incorrect behavior when adding a number already covered by an existing interval?

medium

A. Missing lines checking if val is already covered by existing intervals

B. Line calculating i = bisect_left(intervals, [val, val])

C. Line checking if intervals is empty and appending [val, val]

D. Line popping intervals[i] after merging two intervals

Solution

1. Step 1: Identify missing coverage check

   The code lacks checks to return early if val is already inside intervals[i-1] or intervals[i].

2. Step 2: Consequence of missing check

   Without this, duplicates or incorrect merges occur, corrupting intervals.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing coverage check causes incorrect behavior [OK]

Hint: Always check if val is already covered before inserting [OK]

Common Mistakes:

• Forgetting coverage check
• Incorrect merge boundaries
• Popping wrong interval

3. What is the time complexity of the optimal greedy algorithm that sorts balloons by their end coordinate and then iterates once to find the minimum number of arrows?

medium

A. O(n)

B. O(n log n)

C. O(n^2)

D. O(log n)

Solution

1. Step 1: Identify sorting cost

   Sorting n intervals by end coordinate takes O(n log n) time.

2. Step 2: Identify iteration cost

   Single pass through sorted intervals is O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Dominant cost is sorting, so total is O(n log n) [OK]

Hint: Sorting dominates; iteration is linear [OK]

Common Mistakes:

• Assuming linear time because of single pass
• Confusing with brute force O(n^2)
• Ignoring sorting cost

4. Suppose the problem changes: intervals can be reused infinitely many times, and you want to count how many intervals contain each point considering unlimited reuse (e.g., intervals repeat periodically). Which modification to the line sweep approach correctly handles this scenario?

hard

A. No change needed; line sweep already counts intervals correctly regardless of reuse.

B. Preprocess intervals to merge overlapping intervals into one, then run line sweep once.

C. Use a segment tree or binary indexed tree to handle repeated intervals efficiently instead of line sweep.

D. Modify events to include multiple copies of intervals explicitly and run line sweep on expanded events.

Solution

1. Step 1: Understand reuse impact

   Infinite reuse means intervals repeat periodically, so naive line sweep with explicit events cannot handle infinite copies.

2. Step 2: Recognize data structure need

   Segment trees or binary indexed trees can efficiently query counts over ranges and handle repeated intervals without enumerating all copies.

3. Step 3: Why other options fail

   No change (A) ignores infinite reuse; merging (B) loses count detail; explicit expansion (D) is infeasible for infinite repeats.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Segment trees handle range queries with repeated intervals efficiently [OK]

Hint: Infinite reuse requires data structures, not event enumeration [OK]

Common Mistakes:

• Assuming line sweep handles infinite repeats
• Trying to expand events explicitly
• Merging intervals loses count accuracy

5. Suppose intervals can be reused multiple times (i.e., you can merge overlapping intervals repeatedly, possibly reusing intervals). Which modification to the merge intervals algorithm correctly handles this scenario?

hard

A. Use the same sorting + one pass merge approach; repeated intervals will be merged naturally.

B. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes.

C. Use a brute force nested loop approach to merge intervals until no overlaps remain.

D. Use a graph-based approach to find connected components of overlapping intervals and merge each component.

Solution

1. Step 1: Understand that reusing intervals means overlaps can form complex connected groups.

   Simple one-pass merge assumes intervals appear once and sorted order suffices.

2. Step 2: Recognize that overlapping intervals form connected components in a graph.

   Building a graph where intervals are nodes and edges represent overlaps allows merging all connected intervals correctly.

3. Step 3: Evaluate options.

   Use the same sorting + one pass merge approach; repeated intervals will be merged naturally. fails because one pass merge assumes no reuse. Sort intervals and repeatedly apply the merge pass until no changes occur, which may take multiple passes. is inefficient and may not terminate quickly. Use a brute force nested loop approach to merge intervals until no overlaps remain. is brute force and inefficient. Use a graph-based approach to find connected components of overlapping intervals and merge each component. correctly models the problem and merges all connected intervals.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Graph connected components capture all overlapping intervals including reuse. [OK]

Hint: Model reuse as graph connected components [OK]

Common Mistakes:

• Assuming one pass merge works with reuse
• Using repeated merges without termination guarantee