Giả sử chúng ta có một danh sách các khoảng trong đó mỗi khoảng giống như [bắt đầu, kết thúc) và chúng ta cũng có một danh sách các chuỗi được gọi là các loại. Bây giờ đối với một i đã cho, các khoảng [i] hiển thị thời gian ai đó đã làm các loại công việc [i] từ [bắt đầu, kết thúc). Hai khoảng cùng loại không bao giờ trùng nhau hoặc chạm nhau. Vì vậy, chúng tôi phải tìm một danh sách hợp nhất được sắp xếp trong đó mỗi mục có [bắt đầu, kết thúc, num_types], cho biết từ đầu đến cuối, số lượng nhiệm vụ đang được thực hiện.
Vì vậy, nếu đầu vào giống như khoảng =[[0, 3], [5, 7], [0, 7]] loại =["giải quyết vấn đề", "tin tức", "chơi trò chơi"], thì đầu ra sẽ là [[0, 3, 2], [3, 5, 1], [5, 7, 2]], vì chúng tôi có một số loại công việc đang được thực hiện:Giữa [0, 3) "giải quyết vấn đề" và " chơi trò chơi ", giữa [3, 5)" chơi trò chơi "và giữa [5, 7)" tin tức "và" chơi trò chơi ".
Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -
-
ev:=một danh sách mới
-
đối với mỗi cặp kết thúc bắt đầu khoảng (s, e) trong khoảng thời gian, thực hiện
-
insert (s, 1) vào cuối ev
-
insert (e, −1) vào cuối ev
-
-
sắp xếp danh sách ev
-
cnt:=0, cuối cùng:=−1
-
ans:=một danh sách mới
-
cho mỗi lần và tham số gia tăng của sự kiện (t, inc) trong ev, do
-
nếu t không giống với cuối cùng và cnt không giống 0, thì
-
cnt:=cnt + inc
-
-
cuối cùng:=t
-
-
trả lại ans
Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -
Ví dụ
class Solution: def solve(self, intervals, jobs): ev = [] for s, e in intervals: ev.append((s, 1)) ev.append((e, −1)) ev.sort() cnt = 0 last = −1 ans = [] for t, inc in ev: if t != last and cnt != 0: ans.append([last, t, cnt]) cnt += inc last = t return ans ob = Solution() intervals = [ [0, 3], [5, 7], [0, 7] ] types = ["problem solving", "news", "game play"] print(ob.solve(intervals, types))
Đầu vào
[[0, 3],[5, 7],[0, 7]], ["problem solving", "news", "game play"]
Đầu ra
[[0, 3, 2], [3, 5, 1], [5, 7, 2]]