Simurgh's Watch (Hard Version)
Contest: Rayan Programming Contest 2024 - Selection (Codeforces Round 989, Div. 1 + Div. 2)
Difficulty rating: 3500
Tags: greedy, implementation

The only difference between the two versions of the problem is whether overlaps are considered at all points or only at integer points.

The legendary Simurgh, a mythical bird, is responsible for keeping watch over vast lands, and for this purpose, she has enlisted $$$n$$$ vigilant warriors. Each warrior is alert during a specific time segment $$$[l_i, r_i]$$$, where $$$l_i$$$ is the start time (included) and $$$r_i$$$ is the end time (included), both positive integers.

One of Simurgh's trusted advisors, Zal, is concerned that if multiple warriors are stationed at the same time and all wear the same color, the distinction between them might be lost, causing confusion in the watch. To prevent this, whenever multiple warriors are on guard at the same integer moment, there must be at least one color which is worn by exactly one warrior.

So the task is to determine the minimum number of colors required and assign a color $$$c_i$$$ to each warrior's segment $$$[l_i, r_i]$$$ such that, for every (integer) time $$$t$$$ contained in at least one segment, there exists one color which belongs to exactly one segment containing $$$t$$$.

Input format:
The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — the number of test cases.

For each test case:

- The first line contains an integer $$$n$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$) — the number of warriors stationed by Simurgh.
- The next $$$n$$$ lines each contain two integers $$$l_i$$$ and $$$r_i$$$ ($$$1 \leq l_i \leq r_i \leq 10^9$$$) — the start and end times of the warrior's watch segment.

The sum of $$$n$$$ across all test cases does not exceed $$$2 \cdot 10^5$$$.

Output format:
For each test case:

- Output the minimum number of colors $$$k$$$ needed.
- Then, output a line of $$$n$$$ integers $$$c_i$$$ ($$$1 \leq c_i \leq k$$$), where each $$$c_i$$$ is the color assigned to the $$$i$$$-th warrior.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
We can represent each warrior's watch segment as an interval on the X-axis;

In test case 1, the intervals can be colored as shown below (intervals are colored with the selected color; areas are colored if this color occurs exactly once at this point in time):

In test case 2, the intervals can be colored as shown below:

In test case 3, the intervals can be colored as shown below:

Example input:
3
5
1 4
2 8
3 7
5 10
6 9
5
1 5
2 6
3 7
4 7
6 7
5
4 9
8 17
2 15
12 19
6 13

Example output:
2
1 2 2 1 2
2
1 2 2 2 1
3
1 1 2 3 1

Editorial:
Step 1: Verifying the Possibility of Coloring with One Color
It is easy to check if the solution can be achieved with only one color. For any time point $$$x$$$, there must be at most one interval containing $$$x$$$, since if multiple intervals contain $$$x$$$, they must be colored differently.
Step 2: Solving with Three Colors
A simple strategy is to solve the problem using three colors. First we color some intervals with colors 1 and 2, then color other with color 3.
For each step, we find the leftmost point that has not been colored yet, and color the segment that contains this point. We always choose the interval with the largest endpoint that contains the current point.
By coloring the intervals alternately with colors 1 and 2, we ensure that all points are covered by exactly one of these two colors.
Step 3: Checking if Two Colors are Sufficient
Now, we check if we can color the intervals with just two colors.
For some point $$$x$$$, suppose we have already colored the intervals $$$[l_i, r_i]$$$ with $$$l_i \leq x$$$, such that all points before $$$x$$$ have a unique color. At each step, we only need to determine which of the intervals that contain $$$x$$$ can have a unique color.
The key observation is that if an interval can be uniquely colored at time $$$x$$$, it can also remain uniquely colored for all times $$$t$$$ such that $$$x \leq t \leq r_i$$$.
Lemma:
If an interval $$$[l_i, r_i]$$$ can be uniquely colored at time $$$x$$$, it can also be uniquely colored at all subsequent times $$$t$$$ until $$$r_i$$$.
Proof: Consider coloring the intervals at time $$$x$$$. Intervals starting at $$$x + 1$$$ will be colored with the opposite color to interval $$$i$$$, ensuring that the interval remains uniquely colored at time $$$x+1$$$ as well.
With this lemma, we can conclude that the changes in the coloring are $$$O(n)$$$. It suffices to track the intervals that are added and removed at each point in time.
To efficiently move from time $$$x$$$ to $$$x + 1$$$, we perform the following steps:
• Remove the intervals that have $$$r_i = x$$$ (since they no longer contain $$$x+1$$$).
• Add the intervals that have $$$l_i = x + 1$$$.
• Update the set of intervals that can be uniquely colored at time $$$x+1$$$.
Finally, we observe that only the following points are important for the coloring:
• $$$l_i$$$ and $$$r_i$$$ for each interval.
• $$$l_i - 1$$$ and $$$r_i + 1$$$, since these points mark the boundaries where intervals start or end.
Thus, we can compress the numbers to reduce the range of values we need to process.