โปรแกรมหาช่วงที่ยาวที่สุดจากรายการช่วงใน Python

สมมติว่าเรามีรายการของช่วงเวลาที่แต่ละช่วงอยู่ในรูปแบบ [เริ่ม, สิ้นสุด] เราต้องหาช่วงที่ยาวที่สุดที่เราสามารถทำได้โดยการรวมช่วงเวลาที่ทับซ้อนกันจำนวนเท่าใดก็ได้

ดังนั้น หากอินพุตเป็น [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]] ผลลัพธ์จะเป็น 9 เช่นเดียวกับหลังการรวม เรามีช่วง [1, 9] ของความยาว 9

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

• เรียงลำดับรายการช่วงเวลา
• union :=ช่วงแรกจากรายการช่วงเวลา
• ดีที่สุด :=union[end] - union[start] + 1
• สำหรับแต่ละเวลาเริ่มต้นและเวลาสิ้นสุด e ในช่วงเวลายกเว้นช่วงเวลาแรก ให้ทำ
  • ถ้า s <=union[end] แล้ว
    • ยูเนี่ยน[end] :=สูงสุดของยูเนี่ยน[end] และ e
  • มิฉะนั้น
    • union :=ช่วงใหม่ [s, e]
  • ดีที่สุด :=สูงสุดของสิ่งที่ดีที่สุดและสหภาพ[end] - สหภาพ[เริ่มต้น] + 1
• ผลตอบแทนดีที่สุด

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

ตัวอย่าง

class Solution:
   def solve(self, intervals):
      intervals.sort()
      union = intervals[0]
      best = union[1] - union[0] + 1
      for s, e in intervals[1:]:
         if s <= union[1]:
            union[1] = max(union[1], e)
         else:
            union = [s, e]
            best = max(best, union[1] - union[0] + 1)
      return best
ob = Solution()
intervals = [[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]
print(ob.solve(intervals))

อินพุต

[[1, 6],[4, 9],[5, 6],[11, 14],[16, 20]]

ผลลัพธ์

9