Assign Car Rental Orders to Cars

Given n car-rental orders. Each order contains: an order ID: id a pickup time: start a return time: end A car can serve only one order at a time. Two orders may be assigned to the same car when the first order's return time end is less than or equal to the next order's pickup time start. Design a Car class that stores a car ID and its assigned orders. Assign all orders using as few cars as possible, and return the order IDs assigned to each car. Additionally, there are at most K available cars: If all orders can be assigned using at most K cars, output the assignment. Otherwise, output IMPOSSIBLE. Input Format First line: two integers n K. n is the number of orders. K is the maximum number of available cars. Next n lines: three integers id start end. Output Format If assignment is impossible, print IMPOSSIBLE. Otherwise, print cars in ascending car-ID order, one per line: car_id: order_id1 order_id2 ... Car IDs start from 1 and are assigned in the order cars are first created. Example 1 Input: 4 2 101 1 4 102 2 5 103 4 6 104 5 7 Output: 1: 101 103 2: 102 104 Example 2 Input: 3 1 1 1 3 2 2 4 3 4 5 Output: IMPOSSIBLE Constraints 1 <= n <= 200000 1 <= K <= n 0 <= start < end <= 10^9 All order IDs are distinct. Example Input 4 2 101 1 4 102 2 5 103 4 6 104 5 7 Output 1: 101 103 2: 102 104