Phoenix and Memory
Contest: Codeforces Round 638 (Div. 2)
Difficulty rating: 2600
Tags: data structures, dfs and similar, graphs, greedy

Phoenix is trying to take a photo of his $$$n$$$ friends with labels $$$1, 2, \dots, n$$$ who are lined up in a row in a special order. But before he can take the photo, his friends get distracted by a duck and mess up their order.

Now, Phoenix must restore the order but he doesn't remember completely! He only remembers that the $$$i$$$-th friend from the left had a label between $$$a_i$$$ and $$$b_i$$$ inclusive. Does there exist a unique way to order his friends based of his memory?

Input format:
The first line contains one integer $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$)  — the number of friends.

The $$$i$$$-th of the next $$$n$$$ lines contain two integers $$$a_i$$$ and $$$b_i$$$ ($$$1 \le a_i \le b_i \le n$$$)  — Phoenix's memory of the $$$i$$$-th position from the left.

It is guaranteed that Phoenix's memory is valid so there is at least one valid ordering.

Output format:
If Phoenix can reorder his friends in a unique order, print YES followed by $$$n$$$ integers  — the $$$i$$$-th integer should be the label of the $$$i$$$-th friend from the left.

Otherwise, print NO. Then, print any two distinct valid orderings on the following two lines. If are multiple solutions, print any.

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

Example input:
4
4 4
1 3
2 4
3 4

Example output:
YES
4 1 2 3

Example input:
4
1 3
2 4
3 4
2 3

Example output:
NO
1 3 4 2 
1 2 4 3

Editorial:
There are many many many solutions to this problem (which is cool!). I describe two of them below.
Both solutions first find an arbitrary valid ordering. This can be done in $$$O(n\log{n})$$$ with a greedy algorithm. We can sort the intervals $$$(a_i,b_i)$$$ and sweep from left to right. To see which position that we can assign friend $$$j$$$ to, we process all intervals with $$$a_i \le j$$$ and insert $$$b_i$$$ into a multiset (or similar) structure. We match friend $$$j$$$ to the interval with minimal $$$b_i$$$.
Solution $$$1$$$:
We prove that if there exists more than one valid ordering, we can transform one into another by swapping two friends.
Proof:
In our valid ordering, each friend is assigned a position. We can think of this as a point being assigned to an interval (Friend - point, position - interval). We will prove there exists a cycle of length $$$2$$$ or there exists no cycle at all.
Suppose we have a cycle: each point is on its interval and its predecessor's interval. Let's take the shortest cycle of length at least two. Let $$$q$$$ be the leftmost point, $$$p$$$ be $$$q$$$'s predecessor, and $$$r$$$ be $$$q$$$'s successor.
Case $$$1$$$: $$$q$$$'s interval's right endpoint is to the right of $$$p$$$. $$$p$$$ and $$$q$$$ form a cycle of length $$$2$$$.
Case $$$2$$$: $$$q$$$'s interval's right endpoint is to the left of $$$p$$$. $$$r$$$ must be between $$$q$$$ and $$$p$$$. So, we can remove $$$q$$$ and get a shorter cycle. This is a contradiction.
$$$\square$$$
Denote $$$p_i$$$ as the position that friend $$$i$$$ is assigned to in our arbitrary ordering. Now, we are interested whether or not there exists a friend $$$i$$$ such that there also exists some friend $$$j$$$ with $$$p_j$$$ such that $$$p_i < p_j \le b_{p_i}$$$ and $$$a_{p_j} \le p_i$$$. If there does, we can swap friends $$$i$$$ and $$$j$$$ to make another valid ordering. This can be done with a segment tree (build it with values $$$a_i$$$).
Time Complexity: $$$O(n \log n)$$$
Solution $$$2$$$:
The problem is equivalent to checking if there is a unique perfect matching in the following bipartite graph:
The vertices on the left correspond to position. The vertices on the right correspond to labels of the friends. A directed edge from a position node to a label node exists iff the friend with that label can be at that position.
Find a perfect matching (corresponding to finding any valid assignment) as described above.
The matching is unique iff contracting the edges (merging nodes connected by edges from our perfect matching into one node) in the perfect matching creates a DAG. The reasoning is as follows:
Consider a simpler graph, with only nodes representing positions. We draw a directed edge from node $$$i$$$ to node $$$j$$$ if the friend currently assigned at position $$$i$$$ (from our greedy) can also be assigned to position $$$j$$$. So, if there exists any cycle, we can shift the friends around the cycle to create another valid ordering. In other words, if our graph is a DAG, the perfect matching is unique.
Now, returning back to the bipartite graph, we see that it is essentially the same. By contracting edges, all position nodes are equivalent to the friend node that is assigned to them (from the greedy). So, following an edge from the left side (position) to the right side (friend) puts us back on the left side (position), and this graph corresponds to the simpler version I explained above.
So, this can be done by DFS in $$$O(n^2)$$$, but this is too slow. We can speed it up by storing a set of unvisited vertices and only iterating across those (by binary search on set-like structure). Binary search works because every position corresponds to a range of friends.
Time Complexity: $$$O(n \log{n})$$$