โปรแกรมค้นหาช่วงเวลาโดยการรวมช่วงเป้าหมายใน Python

สมมติว่าเรามีรายการของช่วงเวลาที่ไม่ทับซ้อนกัน โดยจะจัดเรียงตามเวลาสิ้นสุด เรามีเป้าหมายช่วงเวลาอื่น ค้นหาช่วงเวลาสุดท้ายหลังจากรวมเป้าหมายเพื่อให้ช่วงเวลายังคงไม่ทับซ้อนกันและจัดเรียง

ดังนั้น หากอินพุตเป็นช่วง =[[1, 15],[25, 35],[75, 90]], เป้าหมาย =[10, 30] ผลลัพธ์จะเป็น [[1, 35], [ 75, 90]] เมื่อรวมสองช่วงแรก [1, 15] และ [25, 35] เข้าด้วยกัน

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

• ใส่เป้าหมายที่ส่วนท้ายของ iv

• เรียงลำดับ iv ตามเวลาเริ่มต้น

• res :=รายการใหม่ที่มีช่วงแรก

• ผม :=1

• ในขณะที่ฉัน <ขนาดของ iv ทำ

  • ถ้าเวลาเริ่มต้นของ iv[i] <=เวลาสิ้นสุดของช่วงเวลาสุดท้ายของ res แล้ว

    • เวลาสิ้นสุดของช่วงความละเอียดสุดท้าย =สูงสุดของ (เวลาสิ้นสุดของช่วงความละเอียดสุดท้ายและเวลาสิ้นสุดของ iv[i])

  • มิฉะนั้น

    • ใส่ iv[i] ต่อท้าย res

  • ผม :=ผม + 1

• ผลตอบแทน

ตัวอย่าง (Python)

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

class Solution:
   def solve(self, iv, target):
      iv.append(target)
      iv.sort(key=lambda x: x[0])
      res = [iv[0]]
      i = 1
      while i < len(iv):
         if iv[i][0] <= res[-1][1]:
            res[-1][1] = max(res[-1][1], iv[i][1])
         else:
            res.append(iv[i])
         i += 1
      return res
ob = Solution()
intervals = [
   [1, 15],
   [25, 35],
   [75, 90]
]
target = [10, 30]
print(ob.solve(intervals, target))

อินพุต

[[1, 15],[25, 35],[75, 90]], [10, 30]

ผลลัพธ์

[[1, 35], [75, 90]]