โปรแกรมหาจำนวนหลักสูตรสูงสุดที่เราสามารถทำได้ตามช่วงเวลาใน Python?

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

ดังนั้น ถ้า input เท่ากับ times =[[3, 6],[6, 9],[7, 8],[9, 11]] ผลลัพธ์ที่ได้จะเป็น 3 ตามที่เราสามารถลงเรียนรายวิชา [[3 ได้] , 6], [7, 8], [9, 11]]

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

• เรียงลำดับตามเวลาสิ้นสุด

• ตัวนับ :=0, สิ้นสุด :=-1

• สำหรับผมอยู่ในช่วง 0 ถึงขนาดเท่า ทำ

  • ถ้า times[i, 0]> end ไม่ใช่ศูนย์ ดังนั้น

    • เคาน์เตอร์ :=เคาน์เตอร์ + 1

    • สิ้นสุด :=ครั้ง[i, 1]

• เคาน์เตอร์คืนสินค้า

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

ตัวอย่าง

class Solution:
   def solve(self, times):
      times.sort(key=lambda x: x[1])

      counter = 0
      end = -1

      for i in range(len(times)):
         if times[i][0] > end:
            counter += 1
            end = times[i][1]
      return counter

ob = Solution()
times = [
   [3, 6],
   [6, 9],
   [7, 8],
   [9, 11]
]
print(ob.solve(times))

อินพุต

[ [3, 6],[6, 9],[7, 8],[9, 11]]

ผลลัพธ์

3