Okay, so the first step should be to solve the problem where the intervals cannot wrap around (it is common for problems with/without wrapping around intervals to have very similar solutions), so I will go over that first:

First of all, consider the easy case when all start points are distinct. Then, you can just pick all of the start points and you are done.

Now, a lot of times when you are solving problems of this kind, you will want to select the set of numbers of your answer in increasing order and choose the interval for each one as you go (think of it as moving left to right over a number line and picking up the numbers in your answer as you go). Of course, this will involve reordering the intervals so that the smallest number you choose is actually in the first interval, the second number you choose is in the second interval, and so on. Going back to that easy case, you can just sort the intervals by start point, and this will hold true. This gives you an easy algorithm when the start points are distinct that will give you your list of numbers in increasing order:

sort by start point
answer = {}
for interval e: answer.add(e.start)

Now, what cases make this algorithm not work? The cases when you have multiple intervals with the same start point, of course! So, let's look at a case like that (after sorting by start point):
1 4
1 2
1 1
4 4

Now, just placing them at the start points won't work, so we need to consider other options. So let's add in the following: If we have already used the start point, let's instead add our last number + 1 and hope it's actually in the interval. This is allowed since we are placing numbers in order so we won't have placed anything bigger than our most recent number yet.

So, our list will be: 1 in [1, 4], 2 in [1, 2], 3 in [1, 1], and 4 in [4, 4]. Unfortunately, this is not correct, since 3 is not in [1, 1]. So how can we do better? Well, if you look at the group of intervals that start with 1, we will put the smaller numbers in the intervals that come earlier, so let's put the intervals that end earlier first. In other words, we will not only sort by start point, but will break ties by sorting in increasing order of end point. So, our list of intervals will look like this with the new sorting:
1 1
1 2
1 4
4 4

Let's try that algorithm again with the new sorting and see what we get: 1 in [1, 1], 2 in [1, 2], 3 in [1, 4], and 4 in [4, 4]. And it worked! The algorithm will look like this:

sort intervals by start, breaking ties by end
last = -1
possible = true
answer = {}
for interval e:
{
  next = max(last + 1, e.start)
  if(next > e.end) possible = false
  else answer.add(next)
  last = next
}
print possible ? "YES" : "NO"

But wait! What about a case like this?
1 1
1 5
1 6
2 2

Here, we will assign 1 to [1, 1], 2 to [1, 5], 3 to [1, 6], and 4 to [2, 2], which is wrong, but if we gave the 2 to [2, 2] it would have worked. So once we use up a certain number x, we need to start considering all intervals that start with x + 1, and always take the one with the lowest endpoint. We will need a priority queue for this!

List<Interval> intervals
Sort intervals by start
index = 0
possible = true;
answer = {}
PriorityQueue<Interval> pq; // Sorted in increasing order of end
int nextNumberToPlace = 0;
while(true)
{
  if(pq.isEmpty())
  {
    if(index == n) break;
    else nextNumberToPlace = intervals[index].start;
  }
  while(index < m && intervals[index].start == nextNumberToPlace)
  {
    pq.add(intervals[index]);
    index++;
  }
  answer.add(nextNumberToPlace);
  Interval cur = pq.poll();
  if(nextNumberToPlace > interval.end) possible = false;
  nextNumberToPlace++;
}

Now for the case where the intervals can wrap around! To do that, we will use a very similar process. However, we have to handle the wrapping around somehow. A common technique for this is to consider the range from [0, 2n] instead of [0, n], duplicating our range of possible values. Now, intervals [a, b] that do not wrap around can be treated as both [a, b] and [a+n, b+n], and intervals that do wrap around can be treated as [a, b+n]. Now, the problem is the same thing as before, but we have to satisfy both intervals for the no-wrapping-around case. Note that we might use a different number to satisfy the two intervals that mean the same thing. For example, consider the case below for n = 4:
1 2 2 3 4 1 4 2

Our intervals will be [1, 2], [5, 6], [2, 3], [6, 7], [4, 5], and [4, 6]. Then the algorithm above gives us the solution: 1 for [1, 2], 2 for [2, 3], 4 for [4, 5], 5 for [4, 6], 6 for [5, 6], and 7 for [6, 7]. However, this tells us that we used 1 to satisfy [1, 2], but to satisfy its duplicate interval [5, 6], we used 6, which corresponds to 2 (because it is 2 + n). So which one did we use? It turns out that we can shift our early answers to be 2 for [1, 2] and 3 for [2, 3], and this makes our solution consistent. This will always be possible to do if we find a solution for the problem with both copies of the intervals added in, though I won't go over how to extract the list of numbers (since it's quite a bit more complicated and not a part of this problem). But for this problem, just modify/duplicate the intervals as described and apply the greedy algorithm with the priority queue that I described at the end of the no-wrap-around case above, and this should tell you whether or not it is possible.

too slow :-(

Firstly, let's only consider the queries when L <= R. For a given set of intervals starting at the same point, it can be proved that if there exists a solution, then there is one in which the selected value for the interval having a lower R value will be smaller that the values selected for the others intervals. This is precisely the solution that we will build.

1. Build the set S, that is the set of intervals that start at the smallest value L.
2. Remove from S the interval with smallest R value and select its value L as the value corresponding to it.
3. Set the L value of the remaining elements in S to L + 1. We can't choose L for them since it's already selected.
4. Repeat step 1 until all the elements are processed.

After processing all the elements in the list you will have a solution for the problem. Note that if in some point while performing step 2 you find that the L value of the interval is greater that its R value, then the problem doesn't have any solution.

In order to handle the queries when L > R, let's transform the problem in other equivalent to it, using a widely used technique consisting in duplicating the input range. Instead of having the range (0, n -1), we will have the range (0, 2 * n — 1), and the queries will be transformed in the following way. - L <= R: Transform this into two queries: (L, R) and (L + N, R + N) - L > R: Transform it into one query: (R, L + N)

Note that after this transformation all the queries have the form L <= R and the initial problem has solution iff the second one has one.

The code that you linked above efficiently implements this solution. Actually all what I did was just explain the code to you.

This is a blatant copy of GCPC 2013 problem G: Ringworld. You can get the problem set, the sample input, the secret test data, the solution outlines and some judge solutions at http://gcpc.nwerc.eu/gcpc_2013.php.

It turns out that instead of solving the original problem directly, where the segments are on a circle, we can instead solve the problem where the segments are on a line using the transformation given in the judge solution because of magic Hall's marriage theorem.

First notice that if the original problem is solvable, then n ≤ m and the transformed problem is solvable. The proof of the converse is outlined below.

Using Hall's marriage theorem, it is sufficient to prove that for all subset of ranges . There are two cases to consider.

Case 0: is the whole circle. In this case we just need to check that n ≤ m.

Case 1: is not the whole circle. In this case we can cut the circle at some point not covered by and flatten it. This does not change |W| and . If the transformed problem has a solution, then .

Example input for a single test case:

4 4
0 1
1 2
2 3
3 0

Consider the case where W = {[3, 0], [0, 1]}. In this case is not the whole circle. We can cut the circle at 2 and flatten W to {[3, 4], [4, 5]}.