Minimum Cars to Satisfy Rental Requests + Assignment Records

Problem: Minimum Number of Cars for Rental Requests + Assignment Records You are given N car rental requests. Each request has: pickup_time return_time A single car cannot serve overlapping rentals. If return_time == next_pickup_time, they do not overlap and can be served by the same car. You are also given a Car class with: id rental_record: a list storing the assigned requests in chronological order Tasks: Compute the minimum number of cars needed to satisfy all requests. Produce one valid assignment and store each request into the corresponding car's rental_record. Input (stdin) N pickup1 return1 ... pickupN returnN Output (stdout) First line: minimum number of cars K. Next K lines: car_id: (p1,r1) (p2,r2) ... with records sorted by pickup time. Constraints 1 <= N <= 2e5 0 <= pickup_time < return_time <= 1e9 Examples See the 5 test cases in the Chinese version. Example Input 3 1 3 2 4 4 6 Output 2 0: (1,3) (4,6) 1: (2,4)