Chương trình tìm khoảng thời gian tối thiểu để bao gồm mỗi truy vấn trong Python

Giả sử chúng ta có một danh sách các khoảng, trong đó các khoảng [i] có một cặp (left_i, right_i) đại diện cho khoảng thứ i bắt đầu từ left_i và kết thúc tại right_i (bao gồm cả hai). Chúng tôi cũng có một mảng khác được gọi là truy vấn. Câu trả lời cho truy vấn thứ j là kích thước của khoảng i nhỏ nhất sao cho left_i <=queries [j] <=right_i. Nếu chúng ta không thể tìm thấy khoảng thời gian như vậy, thì trả về -1. Chúng ta phải tìm một mảng chứa câu trả lời cho các truy vấn.

Vì vậy, nếu đầu vào giống như các khoảng =[[2,5], [3,5], [4,7], [5,5]] truy vấn =[3,4,5,6], thì đầu ra sẽ là [3, 3, 1, 4], bởi vì Các truy vấn được xử lý như sau -

• for query =3:Khoảng [3,5] là khoảng nhỏ nhất giữ 3. vì vậy, 5 - 3 + 1 =3.

• for query =4:Khoảng [3,5] là khoảng nhỏ nhất giữ 4. do đó, 5 - 3 + 1 =3.

• for query =5:Khoảng [5,5] là khoảng nhỏ nhất chứa 5. do đó, 5 - 5 + 1 =1.

• for query =6:Khoảng [4,7] là khoảng nhỏ nhất giữ 6. do đó, 7 - 4 + 1 =4.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• khoảng thời gian:=sắp xếp các khoảng thời gian trong danh sách theo thứ tự ngược lại

• h:=một danh sách mới

• res:=một bản đồ mới

• đối với mỗi q trong danh sách truy vấn đã sắp xếp, hãy thực hiện

  • trong khi khoảng thời gian không trống và thời gian kết thúc của khoảng thời gian cuối cùng <=q, thực hiện

    • (i, j):=khoảng thời gian cuối cùng trong khoảng thời gian, và xóa nó

    • nếu j> =q, thì

      • chèn cặp (j-i + 1, j) vào heap h

  • trong khi h không trống và thời gian kết thúc của khoảng trên cùng trong h

    • xóa phần tử trên cùng khỏi h

  • res [q]:=thời gian bắt đầu của khoảng trên cùng của h nếu h không trống, ngược lại -1

• trả về danh sách res [q] cho tất cả q trong các truy vấn

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn

import heapq
def solve(intervals, queries):
   intervals = sorted(intervals)[::-1]
   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))

Đầu vào

[[2,5],[3,5],[4,7],[5,5]], [3,4,5,6]

Đầu ra

[3, 3, 1, 4]