← 返回 google 的题目列表Car Rental Request Scheduling
类型：online_judge
Problem: Car Rental Request Scheduling
You are given N available cars and M rental requests. Each request is a tuple (pickupTime, returnTime, id):
pickupTime: when the customer picks up the car
returnTime: when the customer returns the car
id: a unique request identifier
A car may serve multiple requests as long as their time intervals do not overlap. If one request returns a car at time t and another request picks up a car at exactly time t, they may use the same car.
Assign a car to every request while satisfying the following:
Output the assigned car ID for every request if all requests can be served.
Minimize the number of cars used.
If serving all requests requires more than N cars, output -1.
Car IDs range from 1 to N. When multiple cars are available, assigning any one of them is valid.
Input Format
First line: two integers N M
Next M lines: three integers pickupTime returnTime id
Output Format
Output -1 if all requests cannot be served.
Otherwise, output the number of cars actually used on the first line, followed by M lines in input order, each containing id carId.
Constraints
1 <= N, M <= 2 * 10^5
0 <= pickupTime < returnTime <= 10^9
All id values are distinct.
Example
Input
2 4
1 5 101
5 8 102
2 6 103
8 10 104
One valid output
2
101 1
102 1
103 2
104 1
Example
Input
2 4
1 5 101
5 8 102
2 6 103
8 10 104
Output
2
101 1
102 1
103 2
104 1