The problem
Given intervals and query points, for each query return the size of the smallest interval containing it (size = right − left + 1), or −1 if none does.
Input: shifts [1,4] [2,4] [3,6] [4,4], moments [2, 3, 4, 5] Output: [3, 3, 1, 4]
Picture it
Picture workers’ shifts and moments in a day. Sweep through the moments in time order. Shifts that have started join a heap ordered by length; shifts already over are thrown away from the top. The shortest shift still on top is the answer for that moment.
How to recognise it
- There are many queries against many intervals, and each query asks for the best interval (here the shortest) that contains a point.
- The answers do not depend on the order in which you compute them, so you may answer the queries offline: sort them, sweep from left to right, and put each answer back in its original slot at the end.
- As the sweep moves right, intervals become active when their start is passed and expire when their end is passed. Expired ones never come back.
- "The shortest active interval" is a minimum over a changing set: a min-heap keyed by length.
- Up to 10^5 intervals and 10^5 queries, so checking every interval for every query is too slow.
Start with brute force
For each query, scan every interval, keep those that contain it, and remember the shortest.
def min_interval_brute(intervals, queries):
ans = []
for q in queries:
best = -1
for a, b in intervals:
if a <= q <= b and (best == -1 or b - a + 1 < best):
best = b - a + 1
ans.append(best)
return ans
Time is O(n · q) and extra space O(1) besides the answer. With n = q = 10^5 that is 10^10 checks, roughly ten minutes or more in Python.
From brute force to the idea
- Find the waste. Every query re-examines all intervals, although neighbouring queries see almost the same set of covering intervals.
- Sort both sides. Sort the intervals by start and loop over the queries in increasing order. Index
imarks the next interval that has not started yet. - Add intervals that have started. While
intervals[i][0] <= q, push(length, end)onto a min-heap, where length isb − a + 1. The heap orders by length, so the shortest is on top. - Throw away intervals that have ended. While the top's end is
< q, pop it. Queries only increase, so an interval that ended before this query has ended before every later one too, and can be discarded for good. Expired intervals deeper in the heap stay there until they reach the top; they do no harm because only the top is ever read (this is called lazy deletion). - Answer. The top is now the shortest interval that started at or before q and ends at or after q: it contains q. If the heap is empty, the answer is −1.
- Restore the original order. Answers are stored in a dictionary keyed by query value, and the last line reads them back in the input order. Duplicate queries share one answer.
This is the key idea: sort the queries, sweep, push intervals as they start, pop them lazily once they end, and read the shortest from a min-heap.
The key idea
Sort intervals and queries; min-heap by size, discarding expired intervals. O(n log n + q log q).
Python solution
def min_interval(intervals, queries):
intervals.sort()
heap, ans, i = [], {}, 0 # heap of (length, end)
for q in sorted(queries):
while i < len(intervals) and intervals[i][0] <= q:
a, b = intervals[i]
heappush(heap, (b - a + 1, b)); i += 1 # started by now
while heap and heap[0][1] < q:
heappop(heap) # already over
ans[q] = heap[0][0] if heap else -1
return [ans[q] for q in queries]LeetCode adds the imports for you. To run this on your own machine, put this at the top: from heapq import heappush, heappop
In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n · q): every interval is checked for every query | O(1) besides the answer list |
| Offline sweep with a heap (shown code) | O(n log n + q log q): sorting both, plus one push and at most one pop per interval | O(n + q): the heap, the dictionary and the sorted copy of the queries |
Edge cases
- No interval covers a query (
[[2, 3]], query 5): the heap is empty or only holds expired intervals, so the answer is −1. - Query on an end point (
[[1, 4]], queries 1 and 4): both ends are inclusive, so both answers are 4. - Single-point interval (
[[4, 4]], query 4): length 1. - Duplicate queries (
[2, 2]): computed twice, stored once in the dictionary, and both answers are filled in. - Unsorted queries (
[5, 2, 4, 3]against the example's intervals): answers come back in the input order,[4, 3, 1, 3]. - The input is changed:
intervals.sort()reorders the caller's list; the queries are not changed. The code needsfrom heapq import heappush, heappop.
Common mistakes
- Appending answers in sorted query order and returning that list, which puts them in the wrong slots when the queries were not sorted.
- Discarding intervals with
heap[0][1] <= q, which wrongly drops an interval whose end equals the query. - Ordering the heap by end instead of length, which returns the interval that ends first, not the shortest one.
- Trying to delete expired intervals from the middle of the heap, which costs O(n) each time; lazy deletion from the top is enough.
For each query, return how many intervals contain it. For intervals [[1, 4], [2, 4], [3, 6], [4, 4]] and queries [2, 3, 4, 5] the answer is [2, 3, 4, 1]. Describe your approach, then write it if you like.
Compare with our answer
A count does not need a heap. The intervals containing q are those that have started (start ≤ q) minus those that have already ended (end < q); every interval that has ended has also started. Two sorted lists and binary search give both numbers.
from bisect import bisect_left, bisect_right
def count_covering(intervals, queries):
starts = sorted(a for a, b in intervals)
ends = sorted(b for a, b in intervals)
return [bisect_right(starts, q) - bisect_left(ends, q) for q in queries]
Time O((n + q) log n), space O(n), and the answers are already in input order.
A strong answer mentions: "started minus ended", why the ended ones are a subset of the started ones, and bisect_right versus bisect_left for the inclusive ends.
1. Tasks have a time window and a priority. For each of 10^5 query times, return the highest-priority task whose window contains it. Which approach fits best?
This is the same offline sweep with a heap ordered by priority instead of length. Scanning is O(n · q), the latest started task may not be the best or may have ended, and merging windows loses which task is which.
2. Why is it safe to pop an interval from the heap for good once its end is before the current query?
Sorting the queries makes the sweep move only forwards, so "ended before q" stays true for all later queries. The heap is never rebuilt, and an interval can contain many queries.
3. A learner replaces the dictionary with a list, appending each answer inside the loop and returning it. With the example's intervals, which queries now give a wrong result?
The loop runs over sorted(queries), so the list comes out as [3, 4] (the answers for 2, then 5) instead of [4, 3]. When the queries are already sorted, the two orders match.
Score 60% or more and the lesson is marked complete.