How many rooms are needed

greedy scheduling heap sorting science and physics

You are given n meetings, each a half-open interval [s, e): it starts at moment s and ends at moment e, so a meeting that starts exactly when another has ended can take the same room. What is the smallest number of rooms needed to hold all the meetings, and how should they be assigned?

The third and fourth tests are all the earthquakes of magnitude five and above in 2015–2025 from the USGS catalogue. A duty shift is opened for each: an hour for magnitude 5, and twice as long with each further unit of magnitude (six times as long in the fourth test). How many duty crews must there be so that no event is left without its own?

Input

The first line holds n (1 ≤ n ≤ 2·10⁵), then come n lines with integers s and e (0 ≤ s < e ≤ 2·10⁹).

Output

The first line holds the smallest number of rooms k. The second holds n numbers from 1 to k: the room number for each meeting in input order. If there are several correct assignments, print any.

Examples

Example 1

Input

Output

2
1 2 1 1 2 1

Limits

Time · Python: 4000 ms
Time · Go: 1000 ms
Memory: 256 MB
Judging: 8 tests

Walkthrough

Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.

1Hint 1

The lower bound is visible at once: if at some moment d meetings are going on at once, there are at least d rooms. Try to find an assignment for which exactly that many are enough.

2The idea

Go through the meetings in order of start. Give the next meeting any room that has already been freed, and if there is no free one, open a new one. Keep the busy rooms in a heap by the moment they are freed, the earliest on top.

3Walkthrough

Why will there be exactly as many rooms as meetings going on at once at the busiest moment? A new room opens only when all the rooms already open are busy. Let it be the k-th room, opened for a meeting starting at moment s. Each of the k − 1 busy meetings started no later than s (we go by starts) and ends after s (otherwise its room would be free). So at moment s there are k meetings going on at once, and fewer than k rooms will not do. This is a typical technique for greed: the greedy answer matches a lower bound, and it cannot be better.

Careful with the boundary: the intervals are half-open, so a room freed at moment s can already be given to a meeting starting at s. Take all the rooms ending no later than s off the heap.

3+Solution

4Complexity

The sort is O(n log n), and each meeting enters the heap once and leaves once: O(n log n) in all.

5Common mistakes

Counting a touch as an overlap. The meeting [10, 11) does not get in the way of [9, 10). The example in the statement breaks exactly on this: the right answer is 2 rooms.
Going by ends instead of starts. To choose the most meetings for one room you sort by end, but here by start; the two problems are easy to confuse.
Counting only the number. The number of rooms can also be found by a simple pass over “start, end” events, but assigning rooms needs a heap of free rooms.

Algorithms behind it

PAR Technique Greedy algorithms The best step now with no looking back: when it is optimal, when almost, and how to prove it. usually O(n log n): a sort or a heap 2 problems DS Data structure Binary heap The minimum at hand, insertion and extraction in O(log n): the tree in an array that event calendars live on. O(log n) 2 problems