Chương trình tìm số lượng tác vụ đang thực hiện trong từng khoảng thời gian bằng Python

Giả sử chúng ta có danh sách các khoảng thời gian intervals dạng [start, end) và danh sách chuỗi types. Với mỗi i, intervals[i] cho biết thời gian làm việc trên loại tác vụ types[i]. Hai khoảng cùng loại không bao giờ giao nhau. Cần tìm danh sách hợp nhất và sắp xếp, mỗi mục dạng [start, end, num_types] cho biết từ start đến end có num_types tác vụ đang được thực hiện.

Ví dụ: intervals = [[0, 3], [5, 7], [0, 7]], types = ["problem solving", "news", "game play"]. Kết quả: [[0, 3, 2], [3, 5, 1], [5, 7, 2]].

Quy trình giải quyết

1. Tạo danh sách sự kiện ev: với mỗi khoảng (s, e) thêm (s, 1) và (e, -1).
2. Sắp xếp ev.
3. Duyệt qua các sự kiện, giữ biến cnt đếm số tác vụ đang hoạt động và last thời điểm trước.
4. Khi t != last và cnt != 0, thêm đoạn [last, t, cnt] vào kết quả.
5. Cập nhật cnt += inc, last = t.

Ví dụ mã nguồn

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))
# Output: [[0, 3, 2], [3, 5, 1], [5, 7, 2]]

Đầ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]]