โปรแกรมหาช่วงเวลาที่มีการทำงานหลายงานพร้อมกันใน Python

สมมติว่าเรามีรายการช่วงเวลา intervals โดยแต่ละช่วงเป็น [start, end) และรายการสตริงชื่อ types สำหรับ index i ช่วง intervals[i] แสดงเวลาทำงานประเภท types[i] จาก [start, end) ช่วงเวลาของประเภทเดียวกันไม่ทับซ้อนหรือติดกัน เราต้องหารายการรวมที่เรียงลำดับ โดยแต่ละรายการมี [start, end, num_types] แสดงว่าจาก start ถึง end มีงานทำพร้อมกัน num_types งาน

ตัวอย่าง: intervals = [[0, 3], [5, 7], [0, 7]], types = ["problem solving", "news", "game play"] ผลลัพธ์คือ [[0, 3, 2], [3, 5, 1], [5, 7, 2]]

ขั้นตอนการแก้ปัญหา

1. สร้างลิสต์ ev ว่าง
2. สำหรับแต่ละคู่ (s, e) ใน intervals:
   • เพิ่ม (s, 1) เข้า ev
   • เพิ่ม (e, -1) เข้า ev
3. เรียงลำดับ ev
4. กำหนด cnt = 0, last = -1, ans = []
5. สำหรับแต่ละ (t, inc) ใน ev:
   • ถ้า t != last และ cnt != 0:
     • เพิ่ม [last, t, cnt] เข้า ans
   • cnt += inc
   • last = t
6. คืนค่า ans

ตัวอย่างโค้ด Python

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

อินพุต / เอาต์พุต

Input: [[0, 3], [5, 7], [0, 7]], ["problem solving", "news", "game play"]

Output: [[0, 3, 2], [3, 5, 1], [5, 7, 2]]