Chương trình tìm khoảng thời gian bằng cách hợp nhất khoảng thời gian đích trong Python

Giả sử chúng ta có một danh sách các khoảng không trùng nhau. Chúng được sắp xếp dựa trên thời gian kết thúc. Chúng tôi có một mục tiêu khoảng thời gian khác, hãy tìm khoảng thời gian cuối cùng sau khi hợp nhất mục tiêu để các khoảng thời gian vẫn không chồng chéo và được sắp xếp.

Vì vậy, nếu đầu vào giống như khoảng =[[1, 15], [25, 35], [75, 90]], target =[10, 30], thì đầu ra sẽ là [[1, 35], [ 75, 90]] khi hai khoảng đầu tiên [1, 15] và [25, 35] được hợp nhất.

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

• chèn mục tiêu vào cuối iv

• sắp xếp iv dựa trên thời gian bắt đầu

• res:=một danh sách mới với khoảng thời gian đầu tiên

• i:=1

• trong khi tôi

  • nếu thời gian bắt đầu của iv [i] <=thời gian kết thúc của khoảng thời gian cuối cùng của res, thì

    • thời gian kết thúc của khoảng thời gian cuối cùng của res =tối đa của (thời gian kết thúc của khoảng thời gian cuối cùng của res và thời gian kết thúc của iv [i])

  • nếu không,

    • chèn iv [i] vào cuối res

  • i:=i + 1

• trả lại res

Ví dụ (Python)

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

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

Đầu vào

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

Đầu ra

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