โปรแกรมค้นหาช่วงเวลาขั้นต่ำเพื่อรวมแต่ละคิวรีใน Python

สมมติว่าเรามีรายการของช่วงเวลา โดยที่ intervals[i] มีคู่ (left_i, right_i) แทนช่วง ith โดยเริ่มต้นที่ left_i และสิ้นสุดที่ right_i (รวมทั้งสอง) เรายังมีอาร์เรย์อื่นที่เรียกว่าการสืบค้นข้อมูล คำตอบของการสืบค้น jth คือขนาดของช่วงเวลาที่เล็กที่สุด i นั้น left_i <=query[j] <=right_i หากเราไม่พบช่วงเวลาดังกล่าว ให้คืนค่า -1 เราต้องหาอาร์เรย์ที่มีคำตอบสำหรับคำถาม

ดังนั้น หากอินพุตเหมือนช่วงเวลา =[[2,5],[3,5],[4,7],[5,5]] การสืบค้น =[3,4,5,6] ผลลัพธ์จะออกมา เป็น [3, 3, 1, 4] เนื่องจาก แบบสอบถามได้รับการประมวลผลดังนี้ −

• สำหรับข้อความค้นหา =3:ช่วง [3,5] คือช่วงที่เล็กที่สุดที่มี 3 ดังนั้น 5 - 3 + 1 =3

• สำหรับข้อความค้นหา =4:ช่วง [3,5] คือช่วงที่เล็กที่สุดที่มี 4. ดังนั้น 5 - 3 + 1 =3.

• สำหรับข้อความค้นหา =5:ช่วง [5,5] คือช่วงที่เล็กที่สุดที่ถือ 5. ดังนั้น 5 - 5 + 1 =1

• สำหรับข้อความค้นหา =6:ช่วง [4,7] คือช่วงที่เล็กที่สุดที่ถือ 6 ดังนั้น 7 - 4 + 1 =4

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ช่วงเวลา :=เรียงลำดับช่วงเวลาของรายการในลำดับย้อนกลับ

• h :=รายการใหม่

• res :=แผนที่ใหม่

• สำหรับแต่ละ q ในรายการที่เรียงลำดับของแบบสอบถาม ทำ

  • ในขณะที่ช่วงเวลาไม่ว่างและเวลาสิ้นสุดของช่วงเวลาสุดท้าย <=q ทำ

    • (i, j) :=ช่วงสุดท้ายจากช่วงเวลา และลบออก

    • ถ้า j>=q แล้ว

      • ใส่คู่ (j-i+1, j) ลงในฮีป h

  • ในขณะที่ h ไม่ว่างและเวลาสิ้นสุดของช่วงเวลาสูงสุดใน h

    • ลบองค์ประกอบด้านบนออกจาก h

  • res[q] :=เวลาเริ่มต้นของช่วงเวลาสูงสุดของ h หาก h ไม่ว่างเปล่ามิฉะนั้น -1

• ส่งคืนรายการ res[q] สำหรับ q ทั้งหมดในแบบสอบถาม

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น

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))

อินพุต

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

ผลลัพธ์

[3, 3, 1, 4]