โปรแกรมตรวจสอบว่าเราสามารถรับและวางผู้โดยสารทุกคนในรายการที่กำหนดใน Python . ได้หรือไม่

สมมติว่าเรามีเมทริกซ์ที่ชื่อ request_trips ซึ่งแต่ละแถวมี [start_x, end_x, num_passengers] และเรามีค่าความจุด้วย ตอนนี้การเดินทางที่ขอแต่ละครั้งจะขอให้ไปรับผู้โดยสาร num_passengers ที่ start_x และไปส่งที่ end_x นอกจากนี้เรายังมีรถที่มีความจุที่ให้ไว้และเริ่มต้นที่ตำแหน่ง x =0 เราต้องการรับผู้โดยสารทุกคนและสามารถเคลื่อนที่ได้เฉพาะด้านขวาเท่านั้นเราต้องตรวจสอบว่าสามารถรับและวางได้ทุกคนหรือไม่

ดังนั้น หากอินพุตเหมือน trips =[[1, 25, 2], [3, 4, 3],[5, 12, 3]] ความจุ =6 เอาต์พุตจะเป็น True

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

• เหตุการณ์ :=รายการใหม่

• สำหรับแต่ละชุด (sx, ex, np) ในการเดินทาง ทำ

  • แทรกคู่ (sx, np) ที่ส่วนท้ายของเหตุการณ์

  • แทรกคู่ (เช่น −np) ที่ส่วนท้ายของเหตุการณ์

• แบก :=0

• สำหรับแต่ละคู่ (loc, delta) ในรายการเหตุการณ์ (เรียงตามลำดับ) ทำ

  • แบก :=แบก + เดลต้า

  • ถ้าแบก> ความจุ แล้ว

    • คืนค่าเท็จ

• คืนค่า True

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

ตัวอย่าง

class Solution:
   def solve(self, trips, capacity):
      events = []
      for sx, ex, np in trips:
         events.append((sx, np))
         events.append((ex, -np))
      carrying = 0
      for loc, delta in sorted(events):
         carrying += delta
         if carrying > capacity:
            return False
      return True
ob = Solution()
trips = [
   [1, 25, 2],
   [3, 4, 3],
   [5, 12, 3]
]
capacity = 6
print(ob.solve(trips, capacity))

อินพุต

trips = [
[1, 25, 2],
[3, 4, 3],
[5, 12, 3] ]
capacity = 6

ผลลัพธ์

True