मान लीजिए हमारे पास requested_trips नामक एक मैट्रिक्स है जहां प्रत्येक पंक्ति में [start_x, end_x, num_passengers] होता है, और हमारे पास एक क्षमता मान भी है। अब प्रत्येक अनुरोधित ट्रिप start_x पर num_passengers यात्रियों को पिकअप करने और उन्हें end_x पर ड्रॉप करने के लिए कहती है। हमारे पास दी गई क्षमता वाली एक कार है, और हम x = 0 पर शुरू करते हैं। हम हर यात्री को पिकअप करना चाहते हैं और केवल दाईं ओर जा सकते हैं, हमें यह जांचना है कि क्या हम सभी को पिकअप और ड्रॉप ऑफ कर सकते हैं।
तो, यदि इनपुट trips = [[1, 25, 2], [3, 4, 3], [5, 12, 3]], capacity = 6 जैसा है, तो आउटपुट True होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
- events := एक नई सूची
- प्रत्येक सेट (sx, ex, np) ट्रिप्स में के लिए, करें
- (sx, np) जोड़ी को events के अंत में डालें
- (ex, -np) जोड़ी को events के अंत में डालें
- carrying := 0
- घटनाओं की सॉर्ट की गई सूची में प्रत्येक जोड़ी (loc, delta) के लिए, करें
- carrying := carrying + delta
- यदि carrying > capacity, तो False लौटाएं
- 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
