Minimum Interval to Include Each Query

📋

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
}

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

Try testing your solution with empty intervals and single-element intervals to ensure base cases are handled.

Consider cases where multiple intervals cover the same query; check if your solution picks the smallest interval length.

Think about how sorting intervals and queries and using a min-heap can reduce complexity from O(n*m) to O(n log n + m log n).

t1_01basic

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

Expected[3,3,1,4]

⏱ Performance - must finish in 2000ms

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.

💡 Consider checking each query against all intervals to find which include it.

💡 Use brute force to find the minimum length interval covering each query.

💡 For each query, track the smallest interval length that contains it; if none, return -1.

Why it failed: Incorrect output means intervals not checked properly for inclusion or minimum length not tracked; fix by ensuring for each query you check all intervals and update minimum length only if interval covers query.

✓ Correctly finds minimum interval length covering each query.

t1_02basic

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

Expected[3,5,2,-1]

⏱ Performance - must finish in 2000ms

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.

💡 Sort intervals or queries is not required for brute force but helps in optimized solutions.

💡 Check each query against all intervals to find coverage and minimum length.

💡 Return -1 if no interval covers the query.

Why it failed: If output is wrong, likely intervals not checked correctly for each query or minimum length not updated properly; fix by iterating all intervals for each query and updating minimum length only if interval covers query.

✓ Correctly identifies smallest interval length or -1 for each query.

t2_01edge

Input{"intervals":[],"queries":[0,5,10]}

Expected[-1,-1,-1]

⏱ Performance - must finish in 2000ms

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

💡 Check behavior when intervals list is empty.

💡 Ensure code handles empty intervals without errors and returns -1 for all queries.

💡 Return -1 for each query if no intervals exist.

Why it failed: Code crashes or returns wrong values when intervals are empty; fix by adding a check for empty intervals and returning -1 for all queries.

✓ Handles empty intervals correctly by returning -1 for all queries.

t2_02edge

Input{"intervals":[[5,5]],"queries":[5,4,6]}

Expected[1,-1,-1]

⏱ Performance - must finish in 2000ms

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

💡 Test intervals where start equals end (zero length intervals).

💡 Check if queries exactly equal to interval start/end are included.

💡 Return length 1 for queries exactly at zero-length intervals, else -1.

Why it failed: Fails to include queries exactly at zero-length intervals or miscalculates length; fix by including intervals where start == end and length = 1.

✓ Correctly handles zero-length intervals and query inclusion.

t2_03edge

Input{"intervals":[[0,0],[10,10],[5,5]],"queries":[0,5,10,7]}

Expected[1,1,1,-1]

⏱ Performance - must finish in 2000ms

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

💡 Test multiple zero-length intervals at different points.

💡 Ensure queries matching these points return length 1.

💡 Return -1 for queries not covered by any interval.

Why it failed: Fails to handle multiple zero-length intervals or returns wrong length; fix by checking each query against all intervals including zero-length ones.

✓ Correctly returns length 1 for queries at zero-length intervals and -1 otherwise.

t3_01corner

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

Expected[2]

⏱ Performance - must finish in 2000ms

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

💡 Beware of greedy approaches that pick first covering interval without checking all.

💡 Check all intervals covering the query to find the smallest length.

💡 Return the minimum length among all intervals that include the query.

Why it failed: Greedy approach picks first covering interval instead of smallest; fix by checking all intervals covering query and selecting minimum length.

✓ Correctly finds smallest interval length covering query despite nested intervals.

t3_02corner

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

Expected[3]

⏱ Performance - must finish in 2000ms

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

💡 Check if multiple intervals with same length covering query are handled correctly.

💡 Ensure minimum length is returned even if multiple intervals tie.

💡 Return the length value, not the interval itself.

Why it failed: Fails to handle multiple intervals with same length or returns wrong length; fix by comparing lengths and returning minimum length value.

✓ Correctly returns minimum length even when multiple intervals tie.

t3_03corner

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

Expected[2]

⏱ Performance - must finish in 2000ms

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

💡 Check intervals that share boundary points with queries.

💡 Ensure intervals including query at start or end are counted.

💡 Return minimum length among all intervals covering the query.

Why it failed: Fails to include intervals where query equals start or end boundary; fix by using inclusive condition start <= query <= end.

✓ Correctly includes intervals covering query at boundaries.

t4_01performance

Input{"_description":"n=100000 at constraint boundary - executor generates this input"}

Expectednull

⏱ 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.

💡 Brute force O(n*m) will time out; use sorting and min-heap to optimize.

💡 Sort intervals and queries, use a min-heap to track active intervals by length.

💡 Remove intervals from heap when they no longer cover the current query.

Why it failed: TLE due to brute force O(n*m) complexity; fix by implementing sorting of intervals and queries plus min-heap active interval tracking for O(n log n + m log n) complexity.

✓ Efficient O(n log n + m log n) solution passes within time limit.

Practice

1. You are given a list of non-overlapping intervals sorted by their start times, and a new interval to insert. Which approach guarantees an optimal solution that correctly merges overlapping intervals after insertion?

easy

A. Use a greedy approach that inserts the new interval at the end and merges overlapping intervals in one pass without sorting.

B. Iterate through intervals and insert the new interval in the correct position without sorting, then merge overlapping intervals.

C. Use dynamic programming to find the minimal set of merged intervals after insertion.

D. Append the new interval, sort all intervals by start time, then merge overlapping intervals in one pass.

Solution

1. Step 1: Understand the problem constraints

   The intervals are sorted and non-overlapping initially, but inserting a new interval may cause overlaps.

2. Step 2: Identify the approach that guarantees correct merging

   Appending and then sorting ensures the new interval is placed correctly relative to others, allowing a single pass merge to handle all overlaps reliably.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Sorting after insertion ensures correct order for merging [OK]

Hint: Sort after insertion to guarantee correct merge order [OK]

Common Mistakes:

• Assuming intervals remain sorted after insertion without sorting
• Trying to merge without sorting leads to missed overlaps
• Using DP unnecessarily complicates the problem

2. 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

3. You are given a list of time intervals representing booked meeting rooms. Your task is to combine all overlapping intervals into the minimum number of non-overlapping intervals. Which algorithmic approach guarantees an optimal and efficient solution for this problem?

easy

A. Use a greedy approach that always merges the earliest starting interval with the next one without sorting.

B. Sort intervals by start time and then merge overlapping intervals in a single pass.

C. Use dynamic programming to find the maximum number of non-overlapping intervals and then merge accordingly.

D. Check every pair of intervals with nested loops to merge overlaps until no overlaps remain.

Solution

1. Step 1: Understand the problem requires merging overlapping intervals efficiently.

   Sorting intervals by their start time ensures that overlapping intervals are adjacent, enabling a single pass merge.

2. Step 2: Evaluate each option's approach.

   Use a greedy approach that always merges the earliest starting interval with the next one without sorting. fails because without sorting, intervals may be merged incorrectly or missed. Use dynamic programming to find the maximum number of non-overlapping intervals and then merge accordingly. is unrelated as DP is not needed here. Check every pair of intervals with nested loops to merge overlaps until no overlaps remain. is brute force with O(n²) time, inefficient for large inputs. Sort intervals by start time and then merge overlapping intervals in a single pass. correctly sorts and merges in O(n log n) time.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Sorting + one pass merge is the classic optimal pattern for merging intervals. [OK]

Hint: Sort intervals first, then merge in one pass [OK]

Common Mistakes:

• Trying to merge without sorting
• Using nested loops leading to O(n²) time

4. You are given a set of intervals representing horizontal balloons on a number line. Each balloon can be burst by shooting an arrow vertically through any point covered by the balloon's interval. What is the most efficient approach to find the minimum number of arrows needed to burst all balloons?

easy

A. Sort intervals by their end coordinate and greedily shoot arrows at the earliest possible end to cover maximum balloons.

B. Sort intervals by their start coordinate and greedily shoot arrows at the start of each balloon.

C. Use dynamic programming to find the maximum number of overlapping intervals and subtract from total balloons.

D. Use a brute force nested loop to check all pairs of intervals for overlaps and count arrows accordingly.

Solution

1. Step 1: Understand the problem constraints

   The problem requires minimizing arrows to burst all balloons, which translates to covering intervals with minimum points.

2. Step 2: Identify the optimal greedy strategy

   Sorting by end coordinate allows shooting an arrow at the earliest finishing balloon's end, covering all overlapping balloons starting before that point.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Sorting by end coordinate ensures minimal arrows by maximizing coverage [OK]

Hint: Sort intervals by end to greedily cover overlaps [OK]

Common Mistakes:

• Sorting by start coordinate and shooting at start misses optimal overlaps
• Using DP unnecessarily complicates the problem
• Brute force is too slow for large inputs

5. Examine the following buggy code for Employee Free Time. Which line contains the subtle bug causing incorrect free time intervals?

medium

A. Line appending end event with (interval[1], -1)

B. Line appending start event with (interval[0], 1)

C. Line updating prev = time inside loop

D. Line sorting events with key=lambda x: (x[0], -x[1])

Solution

1. Step 1: Understand sorting order impact

   End events must come before start events at same time to avoid false free intervals.

2. Step 2: Identify bug in sorting key

   Sorting with key (x[0], -x[1]) puts start events before end events at ties, causing incorrect free time detection.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Correct sorting is (x[0], x[1]) to put end events before start [OK]

Hint: End events must sort before start events at same time [OK]

Common Mistakes:

• Sorting start before end events at same timestamp