Bird
Raised Fist0
Interview PrepintervalsmediumAmazonGoogle

Remove Covered Intervals

Choose your preparation mode4 modes available
</>
IDE
def remove_covered_intervals(intervals: list[list[int]]) -> int:public int removeCoveredIntervals(int[][] intervals)int removeCoveredIntervals(vector<vector<int>>& intervals)function removeCoveredIntervals(intervals)
def remove_covered_intervals(intervals):
    # Write your solution here
    pass
class Solution {
    public int removeCoveredIntervals(int[][] intervals) {
        // Write your solution here
        return 0;
    }
}
#include <vector>
using namespace std;

int removeCoveredIntervals(vector<vector<int>>& intervals) {
    // Write your solution here
    return 0;
}
function removeCoveredIntervals(intervals) {
    // Write your solution here
}
0/10
Common Bugs to Avoid
Wrong: 3Failing to remove covered intervals due to incorrect sorting order or coverage condition.✅ Sort intervals by start ascending and end descending, then track max end to detect coverage.
Wrong: 0Incorrect handling of empty or single interval input, returning zero instead of correct count.✅ Add explicit checks for empty and single-element inputs to return correct counts.
Wrong: 3Not removing duplicates or treating identical intervals as uncovered.✅ Treat identical intervals as covered except one; ensure coverage condition includes equality.
Wrong: 4Greedy approach counting intervals without coverage check, leading to overcount.✅ Implement coverage detection by sorting and tracking max end to exclude covered intervals.
Wrong: TLEUsing brute force nested loops causing quadratic time complexity.✅ Optimize to O(n log n) by sorting intervals and performing a single pass coverage check.
✓
Test Cases
t1_01basic
Input{"intervals":[[1,4],[2,8],[3,6]]}
Expected2

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

t1_02basic
Input{"intervals":[[1,4],[1,2],[3,4]]}
Expected1

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

t2_01edge
Input{"intervals":[]}
Expected0

Empty input means no intervals remain.

t2_02edge
Input{"intervals":[[5,10]]}
Expected1

Single interval cannot be covered by any other, so it remains.

t2_03edge
Input{"intervals":[[1,5],[1,5],[1,5]]}
Expected1

All intervals are identical; only one remains after removing covered duplicates.

t2_04edge
Input{"intervals":[[1,2],[3,4],[5,6],[10,20]]}
Expected4

No intervals cover any other; all remain.

t3_01corner
Input{"intervals":[[1,10],[2,3],[4,5],[6,7],[8,9]]}
Expected1

All smaller intervals are covered by [1,10], so only one remains.

t3_02corner
Input{"intervals":[[1,4],[2,8],[3,6]]}
Expected2

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

t3_03corner
Input{"intervals":[[1,10],[2,6],[3,5],[5,7]]}
Expected1

All intervals except [1,10] are covered by it, so only one remains.

t4_01performance
Input{"intervals":[[0,1000],[1,1001],[2,1002],[3,1003],[4,1004],[5,1005],[6,1006],[7,1007],[8,1008],[9,1009],[10,1010],[11,1011],[12,1012],[13,1013],[14,1014],[15,1015],[16,1016],[17,1017],[18,1018],[19,1019],[20,1020],[21,1021],[22,1022],[23,1023],[24,1024],[25,1025],[26,1026],[27,1027],[28,1028],[29,1029],[30,1030],[31,1031],[32,1032],[33,1033],[34,1034],[35,1035],[36,1036],[37,1037],[38,1038],[39,1039],[40,1040],[41,1041],[42,1042],[43,1043],[44,1044],[45,1045],[46,1046],[47,1047],[48,1048],[49,1049],[50,1050],[51,1051],[52,1052],[53,1053],[54,1054],[55,1055],[56,1056],[57,1057],[58,1058],[59,1059],[60,1060],[61,1061],[62,1062],[63,1063],[64,1064],[65,1065],[66,1066],[67,1067],[68,1068],[69,1069],[70,1070],[71,1071],[72,1072],[73,1073],[74,1074],[75,1075],[76,1076],[77,1077],[78,1078],[79,1079],[80,1080],[81,1081],[82,1082],[83,1083],[84,1084],[85,1085],[86,1086],[87,1087],[88,1088],[89,1089],[90,1090],[91,1091],[92,1092],[93,1093],[94,1094],[95,1095],[96,1096],[97,1097],[98,1098],[99,1099]]}
⏱ Performance - must finish in 2000ms

n=100 intervals with length 1000 each, O(n log n) sorting + O(n) coverage check must complete within 2s.

Practice

(1/5)
1. Consider the following Python code that determines if a person can attend all meetings given a list of intervals. What is the return value when the input is [[7,10],[2,4]]?
from typing import List

def can_attend_meetings(intervals: List[List[int]]) -> bool:
    intervals.sort(key=lambda x: x[0])
    end = float('-inf')
    for interval in intervals:
        if interval[0] < end:
            return False
        end = interval[1]
    return True

print(can_attend_meetings([[7,10],[2,4]]))
easy
A. None
B. False
C. Raises an exception
D. True

Solution

  1. Step 1: Sort intervals by start time

    Input [[7,10],[2,4]] becomes [[2,4],[7,10]].
  2. Step 2: Iterate and check overlaps

    Initialize end = -inf. First interval start=2 > -inf, update end=4. Second interval start=7 > 4, update end=10. No overlaps found, return True.
  3. Final Answer:

    Option D -> Option D
  4. Quick Check:

    Intervals sorted and no overlaps detected [OK]
Hint: Sort then check if current start < previous end [OK]
Common Mistakes:
  • Confusing return value due to unsorted intervals
2. 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
3. Examine the following buggy code for interval intersections:
def intervalIntersection(A, B):
    i, j = 0, 0
    result = []
    while i < len(A) and j < len(B):
        if A[i][1] <= B[j][0]:
            i += 1
        elif B[j][1] < A[i][0]:
            j += 1
        else:
            start = max(A[i][0], B[j][0])
            end = min(A[i][1], B[j][1])
            result.append([start, end])
            if A[i][1] < B[j][1]:
                i += 1
            else:
                j += 1
    return result
What is the bug in this code?
medium
A. The condition 'if A[i][1] <= B[j][0]' should use '<' instead of '<=' to correctly detect touching intervals.
B. The pointer increments inside the else block are reversed; they should increment the pointer with the larger endpoint.
C. The overlap condition should check 'start < end' instead of 'start <= end' to avoid zero-length intervals.
D. The code does not handle empty input lists, which can cause runtime errors.

Solution

  1. Step 1: Analyze overlap condition

    Using '<=' excludes intervals that touch at a point (e.g., end == start), missing valid intersections.
  2. Step 2: Correct condition

    Changing to '<' ensures intervals that share a boundary point are considered intersecting.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Inclusive endpoints require '<' not '<=' to detect touching intervals [OK]
Hint: Check boundary conditions carefully for inclusive intervals [OK]
Common Mistakes:
  • Using <= instead of <
  • Reversing pointer increments
  • Ignoring empty inputs
4. What is the time complexity of the optimal in-place merge intervals algorithm that first sorts the intervals and then merges them in one pass?
medium
A. O(n log n) due to the sorting step dominating the runtime
B. O(n) because merging is done in a single pass
C. O(n²) because each interval is compared with all others during merging
D. O(n log n) because merging requires binary searches for overlaps

Solution

  1. Step 1: Identify the sorting step complexity.

    Sorting n intervals by start time takes O(n log n) time.
  2. Step 2: Analyze the merging step complexity.

    Merging intervals in one pass is O(n), which is dominated by sorting.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Sorting dominates overall complexity, merging is linear. [OK]
Hint: Sorting dominates, merging is linear [OK]
Common Mistakes:
  • Ignoring sorting cost
  • Assuming nested comparisons cause O(n²)
5. Suppose the problem is modified so that intervals can be reused multiple times for different queries, and queries can be negative integers. Which modification to the binary search + preprocessing approach is necessary to handle this variant correctly and efficiently?
hard
A. Preprocess intervals by length and use a segment tree to query coverage efficiently for negative and repeated queries.
B. No change needed; the original approach works for reuse and negative queries.
C. Sort queries and intervals, use a min-heap to maintain active intervals covering queries in order.
D. Use brute force checking each interval for each query since reuse breaks binary search assumptions.

Solution

  1. Step 1: Identify challenges with reuse and negative queries

    Negative queries require data structures supporting arbitrary ranges; reuse means intervals must be efficiently queried multiple times.
  2. Step 2: Choose appropriate data structure

    Segment tree or interval tree allows efficient coverage queries over any integer range and supports multiple queries efficiently.
  3. Step 3: Why other options fail

    Min-heap approach requires sorting queries and intervals but doesn't handle negative queries well; brute force is inefficient; original approach assumes positive queries and no reuse.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Segment tree supports arbitrary queries and reuse efficiently [OK]
Hint: Segment tree handles arbitrary queries and reuse [OK]
Common Mistakes:
  • Assuming original approach works unchanged
  • Using min-heap without sorting queries
  • Resorting to brute force unnecessarily
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