โปรแกรมค้นหาว่าทำงานกี่งานใน Python . ในช่วงเวลาใด

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

ดังนั้นหากอินพุตเหมือนช่วงเวลา =[ [0, 3], [5, 7], [0, 7] ] types =["การแก้ปัญหา", "ข่าว", "การเล่นเกม"] ผลลัพธ์จะออกมา เป็น [[0, 3, 2], [3, 5, 1],[5, 7, 2]] เนื่องจากเรามีงานบางประเภทที่กำลังทำอยู่:ระหว่าง [0, 3) "การแก้ปัญหา" และ " เล่นเกม" ระหว่าง [3, 5) "เล่นเกม" และระหว่าง [5, 7) "ข่าว" กับ "เล่นเกม"

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• ev :=รายการใหม่

• สำหรับแต่ละช่วงเริ่มต้นคู่สิ้นสุด (s, e) ในช่วงเวลา ให้ทำ

  • แทรก (s, 1) ที่ส่วนท้ายของ ev

  • แทรก (e, −1) ที่ส่วนท้ายของ ev

• เรียงลำดับรายการ ev

• cnt :=0, สุดท้าย :=-1

• ans :=รายการใหม่

• สำหรับแต่ละครั้งและพารามิเตอร์ที่เพิ่มขึ้นของเหตุการณ์ (t, inc) ใน ev ให้ทำ

  • ถ้า t ไม่เหมือนกับครั้งสุดท้าย และ cnt ไม่เหมือนกับ 0 ดังนั้น

    • cnt :=cnt + inc

  • สุดท้าย :=t

• กลับมาอีกครั้ง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

ตัวอย่าง

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

อินพุต

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

ผลลัพธ์

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