LeetCode 1851 · Intervals

Minimum Interval to Include Each Query, explained with a picture

The shortest shift that covers each moment.

HardIntervals
▶ Watch it step by step

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

  1. Find the waste. Every query re-examines all intervals, although neighbouring queries see almost the same set of covering intervals.
  2. Sort both sides. Sort the intervals by start and loop over the queries in increasing order. Index i marks the next interval that has not started yet.
  3. Add intervals that have started. While intervals[i][0] <= q, push (length, end) onto a min-heap, where length is b − a + 1. The heap orders by length, so the shortest is on top.
  4. 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).
  5. 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.
  6. 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

ApproachTimeSpace
Brute forceO(n · q): every interval is checked for every queryO(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 intervalO(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 needs from 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.
Your turn: count the covering intervals

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.

Check what stuck

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?

2. Why is it safe to pop an interval from the heap for good once its end is before the current query?

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?

Score 60% or more and the lesson is marked complete.