How do you solve Minimum Interval to Include Each Query on LeetCode?

Minimum Interval to Include Each Query (LeetCode #1851) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n + m log m) time complexity and O(n) space complexity. Key insight: Sorting intervals and queries helps to efficiently manage which intervals can contain which queries.

What is the brute force solution for Minimum Interval to Include Each Query?

The brute force approach for Minimum Interval to Include Each Query is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach checks each query against all intervals to find the smallest interval that contains the query. This is straightforward but inefficient, especially with many queries and intervals. The optimal Optimal Solution approach improves this to O(n log n + m log m).

What are the interview tips for Minimum Interval to Include Each Query?

Explain your thought process clearly when discussing your approach. Be prepared to discuss the trade-offs between different approaches. Practice writing clean and efficient code under time constraints.

What are common mistakes when solving Minimum Interval to Include Each Query?

Not sorting the intervals and queries, which leads to inefficient checks. Failing to manage the priority queue correctly, leading to incorrect results.

#1851

Minimum Interval to Include Each Query

Hard

ArrayBinary SearchSweep LineSortingHeap (Priority Queue)SortingHeap (Priority Queue)Binary Search

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n + m log m)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n + m log m)Space O(n)

By sorting the intervals and using a priority queue, we can efficiently manage the intervals that can contain each query. This allows us to quickly find the smallest interval for each query.

⚙️

Algorithm

6 steps

1Step 1: Sort the intervals by their starting point.
2Step 2: Create a list of queries with their original indices and sort them.
3Step 3: Use a priority queue to keep track of the intervals that can contain the current query.
4Step 4: For each query, add all intervals that start before or at the query to the priority queue.
5Step 5: Remove intervals from the priority queue that end before the current query.
6Step 6: The smallest interval in the priority queue will be the answer for the current query.

solution.py17 lines

1import heapq
2
3def minInterval(intervals, queries):
4    intervals.sort(key=lambda x: x[0])
5    queries_with_index = sorted((q, i) for i, q in enumerate(queries))
6    result = [-1] * len(queries)
7    min_heap = []
8    j = 0
9    for query, index in queries_with_index:
10        while j < len(intervals) and intervals[j][0] <= query:
11            heapq.heappush(min_heap, (intervals[j][1] - intervals[j][0] + 1, intervals[j][1]))
12            j += 1
13        while min_heap and min_heap[0][1] < query:
14            heapq.heappop(min_heap)
15        if min_heap:
16            result[index] = min_heap[0][0]
17    return result

ℹ

Complexity note: The time complexity is O(n log n) for sorting the intervals and O(m log m) for sorting the queries, where n is the number of intervals and m is the number of queries. The space complexity is O(n) due to the priority queue.

1Sorting intervals and queries helps to efficiently manage which intervals can contain which queries.
2Using a priority queue allows us to quickly find the smallest interval size for each query.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.