สมมติว่าเรามีรายการตัวเลข 2 มิติที่เรียกว่าช่วง ซึ่งแต่ละแถวแสดงถึงช่วง [เริ่ม สิ้นสุด] (รวม) สำหรับช่วงเวลา [a, b] (a
ดังนั้น หากอินพุตเป็นเหมือนช่วง =[[15, 20],[30, 50]] ผลลัพธ์จะเป็น 10 เนื่องจากเราสามารถเพิ่มช่วงเวลา [20, 30] ซึ่งเป็นช่วงที่เล็กที่สุดได้
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
class Solution:
def solve(self, intervals):
events = []
for s, e in intervals:
events.append((s, 1))
events.append((e, -1))
events.sort()
curr_status = 0
last = None
interval = [0, 0]
for time, status in events:
if curr_status == 0 and last and time > last:
if interval[0] == 0:
interval[0] = last
interval[1] = time
last = time
curr_status += status
return interval[1] - interval[0]
ob = Solution()
intervals = [[15, 20],[30, 50]] print(ob.solve(intervals))
อินพุต
[[15, 20],[30, 50]]
ผลลัพธ์
10
