Problem H
Hiring and Firing

Image by Gerd Altmann via Pixabay
Amazin’ Inc, an up-and-coming company in e-commerce, has recently optimized its operations to make the most out of its workers. Thanks to state-of-the-art prediction methods, Amazin’ now knows in advance how many workers will be needed each day for the foreseeable future. Using this information they can adjust the size of their workforce on a day-to-day basis by firing and/or hiring workers so that they always have exactly as many as are needed each day. In order to prevent the workers from getting too comfortable and organizing themselves, they will also regularly fire workers and replace them with new ones. For instance, if on some day four more workers are needed than yesterday, Amazin’ might fire $10$ people and then hire $14$ new ones on that day.

Unfortunately, due to labor laws, the firing of workers must follow a last-in-first-out order: the people who have been employed the shortest time must be fired first. Furthermore, a fired person cannot be re-hired within the foreseeable future so it is not possible to circumvent the law by firing some people and then immediately re-hiring some of them.

But this story is actually about HR, not workers! Every day, one employee from the HR department is assigned to be responsible for giving the fired workers the bad news that they are fired, and for then giving the newly hired workers the good news that they are hired. In order to minimize work environment problems in the form of social awkwardness for the HR staff, a policy has been established requiring that the HR person firing an employee must always be a different HR person than the one welcoming them when they were hired.

Now the time has come for the HR department to also optimize itself, by making itself as small as possible. Unlike workers, new HR staff cannot be hired with short notice, so the HR personnel must be permanent employees. What is the smallest number of HR people needed in order to manage all the planned hirings and firings?


The first line of input contains an integer $n$ ($1 \le n \le 10^5$), the length in days of the foreseeable future. Then follow $n$ lines, the $i$th of which contains two integers $f_ i$ and $h_ i$ ($0 \le f_ i, h_ i \le 10^6$) where $f_ i$ is the number of workers fired on day $i$ and $h_ i$ the number of people hired.

The number of workers fired on a day is never larger than the number of currently employed workers (in other words, $f_ i \le \sum _{j=0}^{i-1} h_ j-f_ j$ for all $1 \le i \le n$).


Output a line with an integer $k$, the smallest number of HR people needed. The HR people are arbitrarily given IDs from $1$ to $k$. Then output a line with $n$ integers, the $i$th of which contains the ID of the HR person in charge of the firing and hiring on day $i$. If there is more than one solution, any one will be accepted.

Sample Input 1 Sample Output 1
0 3
1 1
2 1
2 0
1 2 3 2
Sample Input 2 Sample Output 2
0 10
0 5
2 0
0 0
0 100
50 100
1 2 1 2 1 2

Please log in to submit a solution to this problem

Log in