Cho danh sách khoảng (intervals) với intervals[i] = (left_i, right_i) và mảng queries. Câu trả lời cho truy vấn j là kích thước khoảng nhỏ nhất i sao cho left_i ≤ queries[j] ≤ right_i. Nếu không có khoảng nào thỏa mãn, trả về -1.
Ví dụ: intervals = [[2,5],[3,5],[4,7],[5,5]], queries = [3,4,5,6] → output = [3, 3, 1, 4].
Giải thuật (Sort + Heap)
- Sắp xếp intervals giảm dần theo left.
- Sắp xếp queries tăng dần.
- Duyệt từng query q: thêm vào heap (min-heap) các khoảng có left ≤ q, key = (size, right).
- Loại bỏ khỏi heap các khoảng có right < q (không còn chứa q).
- Đỉnh heap là khoảng nhỏ nhất chứa q → lưu kết quả.
Code Python
import heapq
def solve(intervals, queries):
intervals = sorted(intervals)[::-1] # giảm dần left
h = []
res = {}
for q in sorted(queries):
while intervals and intervals[-1][0] <= q:
i, j = intervals.pop()
if j >= q:
heapq.heappush(h, [j - i + 1, j])
while h and h[0][1] < q:
heapq.heappop(h)
res[q] = h[0][0] if h else -1
return [res[q] for q in queries]
intervals = [[2,5],[3,5],[4,7],[5,5]]
queries = [3,4,5,6]
print(solve(intervals, queries)) # [3, 3, 1, 4]
Đầu vào / Đầu ra
Input: [[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]
Output: [3, 3, 1, 4]