পাইথনে কার প্যাসেঞ্জার পিকআপ-ড্রপ সমস্যা সমাধান (সোয়ার্ম অ্যালগরিদম)

দেওয়া ট্রিপ লিস্ট [[start_x, end_x, num_passengers], ...] এবং কার ক্যাপাসিটি। কার x=0 থেকে শুরু করে শুধু ডানে চলে। সব প্যাসেঞ্জারকে পিকআপ ও ড্রপ করা সম্ভব কিনা যাচাই করতে হবে।

উদাহরণ: trips = [[1,25,2], [3,4,3], [5,12,3]], capacity=6 → True।

ইভেন্ট-ভিত্তিক সমাধান (Sweep Line Algorithm)

1. প্রতিটি ট্রিপের জন্য দুটি ইভেন্ট তৈরি: (start_x, +passengers) এবং (end_x, -passengers)।
2. সব ইভেন্ট লোকেশন অনুযায়ী সর্ট করুন।
3. সেকোয়েন্সিয়ালি প্রসেস করুন: carrying += delta। যদি কোনো মুহূর্তে carrying > capacity হয় → False।
4. সব ইভেন্ট প্রসেস হলে 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))  # True

টাইম কমপ্লেক্সিটি: O(n log n) সর্টিং এর কারণে, স্পেস: O(n)। এটি কার শেয়ারিং/রাইড শেয়ারিং সিস্টেমের ক্লাসিক সমস্যা।