Codeforcees Round 283 Div. 2 Problem E - Distributing Parts

Problem Statement:
496E - Distributing Parts

Solution:
This is more for self-reference, I suggest you read the official tutorial on Codeforces for a better discussion on this problem.

This problem is a bipartite matching problem: match smaller "job" segments into bigger container "worker" segments, where each worker segment has certain capacity. If we model each segments as vertices, then we have a graph with \(V\) vertices. This problem cannot be solved efficiently using maxflow algorithm, since V can be very huge, hence there must be some greedy idea behind it. And as I learnt from the editorial, the idea is to consider both jobs and workers in increasing order of their lower bounds. In this iteration, we keep track of a set S of workers that we have encountered, which has the following invariant:
For all i, by the time we reach i-th segment, the lower-bound of this segment is always bigger or equal to any lower bounds of segments in S.

Hence if the i-th segment we are facing is currently a job segment, we just need to find a worker segment in S that has a bigger upper bound than that of the job segment. If there are multiple choices, we must choose the lowest one available. I think this choice can be proven to yield optimal matching by exchange arguments.

If the implementation of S is done by using RB tree, the running time of this algorithm will be \(O(V\lg{V})\).