Bird
Raised Fist0
Interview PrepintervalshardAmazonGoogle

Minimum Interval to Include Each Query

Choose your preparation mode4 modes available
📋
Problem

Imagine you have a set of time intervals representing TV shows and a list of times you want to watch. For each time, you want to find the shortest show that is playing at that moment.

Given a list of intervals where each interval is represented as [start, end], and a list of queries, for each query find the length of the smallest interval that includes the query point. If no such interval exists, return -1 for that query.

1 ≤ number of intervals ≤ 10^51 ≤ number of queries ≤ 10^50 ≤ start_i ≤ end_i ≤ 10^70 ≤ queries[i] ≤ 10^7
Edge cases: No intervals at all → all queries return -1Queries outside all intervals → return -1Intervals with same start and end (zero length) → must handle correctly
</>
IDE
def min_interval_brute_force(intervals: list[list[int]], queries: list[int]) -> list[int]:public int[] minIntervalBruteForce(int[][] intervals, int[] queries)vector<int> minIntervalBruteForce(vector<vector<int>>& intervals, vector<int>& queries)function minIntervalBruteForce(intervals, queries)
def min_interval_brute_force(intervals, queries):
    # Write your solution here
    pass
class Solution {
    public int[] minIntervalBruteForce(int[][] intervals, int[] queries) {
        // Write your solution here
        return new int[queries.length];
    }
}
#include <vector>
using namespace std;

vector<int> minIntervalBruteForce(vector<vector<int>>& intervals, vector<int>& queries) {
    // Write your solution here
    return vector<int>(queries.size(), -1);
}
function minIntervalBruteForce(intervals, queries) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: [-1, -1, -1]Not checking any intervals for queries or returning default -1 without processing.✅ Add iteration over intervals for each query and update minimum length if interval covers query.
Wrong: [3,3,3,4]Not updating minimum length correctly; always returning length of first covering interval.✅ For each query, compare lengths of all covering intervals and return the smallest.
Wrong: [1,1,1,-1]Incorrectly treating zero-length intervals as length 0 instead of 1 or excluding them.✅ Calculate length as end - start + 1, so zero-length intervals have length 1.
Wrong: TLE or timeoutUsing brute force approach for large inputs causing O(n*m) complexity.✅ Implement sorting of intervals and queries and use a min-heap to track active intervals for O(n log n + m log n) complexity.
✓
Test Cases
t1_01basic
Input{"intervals":[[1,4],[2,4],[3,6],[4,4]],"queries":[2,3,4,5]}
Expected[3,3,1,4]

For query 2, intervals [1,4], [2,4], and [3,6] include 2; smallest length is 3 ([2,4]). For 3, smallest is also length 3 ([2,4]). For 4, smallest is length 1 ([4,4]). For 5, only [3,6] includes it, length 4.

t1_02basic
Input{"intervals":[[5,10],[1,3],[7,8],[2,6]],"queries":[1,4,7,11]}
Expected[3,5,2,-1]

Query 1 covered by [1,3] length 3; query 4 covered by [2,6] length 5; query 7 covered by [5,10] length 6 and [7,8] length 2, smallest is 2; query 11 not covered by any interval, so -1.

t2_01edge
Input{"intervals":[],"queries":[0,5,10]}
Expected[-1,-1,-1]

No intervals present, so no query can be covered; all results are -1.

t2_02edge
Input{"intervals":[[5,5]],"queries":[5,4,6]}
Expected[1,-1,-1]

Single interval with zero length at point 5 covers query 5 only; queries 4 and 6 not covered.

t2_03edge
Input{"intervals":[[0,0],[10,10],[5,5]],"queries":[0,5,10,7]}
Expected[1,1,1,-1]

Queries 0,5,10 each covered by zero-length intervals of length 1; query 7 not covered by any interval.

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

Query 5 covered by all intervals; smallest interval is [5,6] length 2.

t3_02corner
Input{"intervals":[[1,3],[2,4],[3,5]],"queries":[3]}
Expected[3]

Query 3 covered by all intervals; smallest length is 3 (all intervals length 3).

t3_03corner
Input{"intervals":[[1,2],[2,3],[3,4]],"queries":[2]}
Expected[2]

Query 2 covered by intervals [1,2] length 2 and [2,3] length 2; smallest length is 2.

t4_01performance
Input{"_description":"n=100000 at constraint boundary - executor generates this input"}
⏱ Performance - must finish in 2000ms

n=100000 intervals and queries at constraint boundary; O(n log n + m log n) solution must complete within 2 seconds.

Practice

(1/5)
1. Consider the following Python code implementing the min-heap approach to find the minimum number of meeting rooms. Given the input intervals = [[0,30],[5,10],[15,20]], what is the value of the heap after processing the second interval (i=1)?
easy
A. [10]
B. [30, 10]
C. [30, 20]
D. [5, 10]

Solution

  1. Step 1: Trace heap after first interval [0,30].

    Heap contains [30] after pushing end time of first meeting.
  2. Step 2: Process second interval [5,10].

    Since 5 < 30 (heap[0]), no pop occurs; push 10. Heap now contains [10, 30] (min-heap property).
  3. Final Answer:

    Option B -> Option B
  4. Quick Check:

    Heap stores end times; after second interval, both 30 and 10 are in heap [OK]
Hint: Heap stores end times; no pop if start < earliest end [OK]
Common Mistakes:
  • Popping when start < earliest end
  • Confusing heap contents order
  • Forgetting to push current interval's end
2. The following code attempts to count intervals containing each point using a line sweep. Identify the bug that causes incorrect counts for points exactly at interval ends.
medium
A. Line adding interval end event should use end + 1 instead of end.
B. Sorting key should sort points before interval starts.
C. Active count should be incremented after processing points, not before.
D. Result array initialization size is incorrect.

Solution

  1. Step 1: Identify event creation for interval ends

    Interval end events use 'end' instead of 'end + 1', so points exactly at interval end are processed after the interval ends.
  2. Step 2: Understand effect on counting

    Because end events are processed at 'end', points at 'end' see active count after decrement, missing that interval.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Changing to end + 1 fixes counting for points at interval ends [OK]
Hint: Interval end event must be at end+1 to include points at end [OK]
Common Mistakes:
  • Using end instead of end+1
  • Misordering events
  • Incorrect active count update
3. 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
4. What is the time complexity of the optimal algorithm that determines if a person can attend all meetings given n intervals, where the algorithm sorts intervals by start time and then checks for overlaps in a single pass?
medium
A. O(n) because we only scan the intervals once after sorting
B. O(n^2) because each interval is compared with all others for overlaps
C. O(n log n) due to sorting the intervals by start time
D. O(log n) because sorting can be done in logarithmic time

Solution

  1. Step 1: Identify sorting cost

    Sorting n intervals by start time takes O(n log n) time.
  2. Step 2: Identify overlap check cost

    Single pass to check overlaps is O(n), which is dominated by sorting.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Sorting dominates total time complexity [OK]
Hint: Sorting dominates complexity -> O(n log n) [OK]
Common Mistakes:
  • Confusing single pass check as O(n log n)
  • Assuming nested loops cause O(n^2) here
5. The following code attempts to merge intervals in-place after sorting. Identify the line that contains a subtle bug causing incorrect results on some inputs.
medium
A. Line 3: intervals.sort(key=lambda x: x[0])
B. Line 9: intervals[index][1] = max(intervals[index][1], intervals[i][1])
C. Line 12: return intervals # missing slicing after in-place merge
D. Line 8: if intervals[i][0] <= intervals[index][1]:

Solution

  1. Step 1: Understand the in-place merge modifies intervals up to index.

    After merging, only intervals[:index+1] are valid merged intervals.
  2. Step 2: Identify the bug in the return statement.

    Returning the entire intervals list without slicing includes extra unmerged intervals, causing incorrect output.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Return intervals[:index+1] to exclude leftover intervals. [OK]
Hint: Return sliced intervals after in-place merge [OK]
Common Mistakes:
  • Forgetting to slice after in-place merge
  • Modifying list while iterating without adjusting index
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