Minimum Interval to Include Each Query

Hard

The problem

You get a list of ranges [left, right] and a list of query numbers. A range contains a query q if left ≤ q ≤ right. The size of a range is right − left + 1. For every query, find the size of the smallest range that contains it, or -1 if no range does, and return the answers in the same order as the queries.

Example 1
Input: intervals = [[1, 4], [2, 4], [3, 6], [4, 4]], queries = [2, 3, 4, 5]
Output: [3, 3, 1, 4]
Query 2: [1, 4] (size 4) and [2, 4] (size 3), so 3. Query 3: [2, 4] again, size 3. Query 4: [4, 4] has size 1. Query 5: only [3, 6] contains it, size 4.
Example 2
Input: intervals = [[2, 3], [2, 5], [1, 8], [20, 25]], queries = [2, 19, 5, 22]
Output: [2, -1, 4, 6]
Query 19 is inside no range. Query 22 is only inside [20, 25], size 6.

Limits

1 ≤ len(intervals), len(queries) ≤ 100,000
1 ≤ left ≤ right ≤ 10,000,000
Queries are not sorted and may repeat

Write it in Go. Try for about 20 minutes on paper first, then open one hint at a time.

Try it here

Write Go. Common packages like fmt and sort are imported for you. Keep the function name and inputs the same.

Hints, one at a time

Nudge

Answer queries in increasing order so you can reuse work between them.

The idea

Sort intervals by start and queries ascending. For each query push every interval starting ≤ q into a min-heap of (size, end); pop intervals whose end < q; the top is the answer.

Target: O((n + q) log n) time

Go function shape

func minInterval(intervals [][]int, queries []int) []int

Reference solution

Tested with go test. Try it yourself first, then compare.

// MinInterval answers each query with the size of the smallest interval containing it, or -1.
// Process queries in increasing order. Push every interval that has started into a min-heap by size, and pop
// intervals that have already ended; the top of the heap is the answer.
func MinInterval(intervals [][]int, queries []int) []int {
	sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
	order := make([]int, len(queries)) // query indexes sorted by value, so answers go back in the original order
	for i := range order {
		order[i] = i
	}
	sort.Slice(order, func(a, b int) bool { return queries[order[a]] < queries[order[b]] })
	ans := make([]int, len(queries))
	h := &intervalHeap{}
	i := 0
	for _, qi := range order {
		q := queries[qi]
		for i < len(intervals) && intervals[i][0] <= q {
			heap.Push(h, [2]int{intervals[i][1] - intervals[i][0] + 1, intervals[i][1]}) // {size, end}
			i++
		}
		for h.Len() > 0 && (*h)[0][1] < q {
			heap.Pop(h) // ended before the query
		}
		if h.Len() == 0 {
			ans[qi] = -1
		} else {
			ans[qi] = (*h)[0][0]
		}
	}
	return ans
}

type intervalHeap [][2]int

func (h intervalHeap) Len() int           { return len(h) }
func (h intervalHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h intervalHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
func (h *intervalHeap) Push(x any)        { *h = append(*h, x.([2]int)) }
func (h *intervalHeap) Pop() any {
	old := *h
	x := old[len(old)-1]
	*h = old[:len(old)-1]
	return x
}

Read the lesson: Intervals