Purr =^..^= Packing Under Range Regulations

#	User	Rating
1	tourist	3993
2	jiangly	3743
3	orzdevinwang	3707
4	Radewoosh	3627
5	jqdai0815	3620
6	Benq	3564
7	Kevin114514	3443
8	ksun48	3434
9	Rewinding	3397
10	Um_nik	3396

#	User	Contrib.
1	cry	167
2	Um_nik	163
3	maomao90	162
3	atcoder_official	162
5	adamant	159
6	-is-this-fft-	158
7	awoo	156
8	TheScrasse	154
9	Dominater069	153
9	nor	153

This is a simple and educational greedy solution to an AtCoder problem.

The following is (abc214_e) Packing Under Range Regulations: (slightly modified)

Problem Statement

There are $$$10^9$$$ boxes numbered $$$1, 2, \ldots, 10^9$$$ and $$$N$$$ balls numbered $$$1, 2, \ldots, N$$$.

Each box can contain at most one ball.

Determine whether it is possible to put all $$$N$$$ balls in the boxes so that the following condition will be satisfied.

For each integer $$$i$$$ from $$$1$$$ through $$$N$$$, the ball numbered $$$i$$$ is in a box numbered between $$$L_i$$$ and $$$R_i$$$ (inclusive).

Constraints

$$$1 \leq N \leq 2 \times 10^5$$$
$$$1 \leq L_i \leq R_i \times 10^9$$$

How to solve it

I suggest you try your best to solve the problem before continuining.

My initial solution

Initially, I tried a more complicated solution based on Hall's Marriage Theorem. However, the problem's editorial outlines a much more elegant solution that we will discuss.

Visualizing the Problem

Imagine you're walking along the boxes from $$$1$$$ to $$$10^9$$$ without turning back. Some of the boxes may have people behind them, each holding a ball to give you. The person with ball $$$i$$$ is behind box $$$L_i$$$. Whenever you encounter a person, you take the ball they're holding.

At any moment you can place any ball you're holding into the box in front of you, including the one just given to you. However, each box can only hold one ball.

But there's a twist: each ball is actually a ticking bomb. Ball $$$i$$$ is a will explode and kill you if you don't put it into a box before passing position $$$R_i$$$.

Understanding the Greedy

The story above is equivalent to the initial problem statement, but presenting it like this helps make the greedy solution more intuitive.

There's never a point in leaving a box empty if you're holding any bombs. You won't be able to come back to it later and leave a bomb there, so you might as well take some weight off your back right now. However, you still have a choice to make: which of the bombs should you discard?

For example, imagine you're holding three bombs that will explode at times $$$7$$$, $$$8$$$, and $$$10$$$. You can discard a single bomb. Which one should you choose?

The correct approach is to always get rid of the bomb closest to exploding. Although this may not be strictly necessary, there's no reason not to do it. It's intuitive to see how this is correct, but let's provide a proof for completeness:

Proof

Consider a configuration of bomb choices where no bombs explode. Let's say that at some point, instead of discarding the bomb closer to exploding, denoted as $$$X$$$, you discard some other bomb $$$Y$$$ that would explode later. You only discard $$$X$$$ at a later time.

If we switch the positions of bombs $$$X$$$ and $$$Y$$$, we would still have a valid configuration. $$$X$$$ would be discarded earlier than before, so it clearly still wouldn't explode. $$$Y$$$ would be discarded later, but it would be discarded in position where $$$X$$$ still wouldn't have exploded, and $$$X$$$ explodes earlier than $$$Y$$$.

With this switch, we obtain a configuration with less "inversions", meaning there are fewer positions where we chose the "wrong" bomb. By repeating this process, we can transform any valid configuration into the one we would get using our greedy approach, without ever making it invalid. Therefore, if a solution exists, our greedy approach is a valid solution.

Implementation

The implementation consists of simulating the situation described above, resulting in an $$$\mathcal{O}(N\log N)$$$ solution. The $$$\log N$$$ factor comes from sorting the balls in our inventory, for example, using a priority queue.

We start from position $$$1$$$ and iterate through the positions up to $$$10^9$$$, taking any balls we encounter and discarding them as possible. Always picking the bomb closer to exploding. If any bomb explodes, there's no solution.

It is important to note that if our inventory is empty, we should skip to the next box where you'll be given a ball.

If you get stuck, refer to the problem's editorial, where a nice implementation can be found.