Problem D is a dual problem of Interval scheduling. If you sort this problem by the right end of each element (in this case b [i]) and do greedy like Interval scheduling, you will get an answer. a problem with Interval scheduling and this seems to be quite another problem, but in fact, it is the same answer. (This problem is called dual problem)

(I)Overview of Interval scheduling : Give M intervals and choose the maximum number of intervals so that no two intervals share the time zone.

(II)Summary of problem D : we would like to skewer all M sections. we want to find the minimum number of skewers.

I will prove that these two answers will be the same.

1. First, if the answer to the interval scheduling problem is k, the k pieces do not share the time zone, so at least k skewers are necessary to stab all them (weak duality)

2. Conversely, it is enough to have k skewers if you skill carefully follow the movement of the greedy method against the interval scheduling problem. Specifically, if you skewer k pieces from the right end for k intervals that you select for the interval scheduling problem, you can skew all the intervals with just k skewers (strong duality)

With this, we can solve this problem by interval scheduling.

The following is an English translation of editorial.

First, sort the pair of (ai, bi) in ascending order about bi. In order of sorting, do the following.

• Define "meeting the request" as "ai ≤ x (the bridge removed immediately before is the x-th bridge from the west)". If the request has already been satisfied, that is, if one or more bridges have already been removed and the request has been satisfied by the bridge removed just before, do not do anything.

• Remove the (bi-1)-th bridge from the west, ie the bridge connecting the (bi-1)-th island and the (bi)-th island from the west, if you still do not meet that request.

At this time, it becomes optimum. For the latter case, one or more of the ai, ai + 1, ..., bi-1 bridge from the west must be removed, but if you remove the bridge before the (bi-1)-th (Assuming it is the x-th bridge from the west), it will not be optimal if you consider the partial problem that will remain after (x + 1)-th and the following islands and bridges problems from the west). Therefore, sorting became a bottleneck and O (nlogn) solved it. Aside: Actually O (n) can solve it. Think about it if you are interested.

The objective is to create as much as less segment from given all the segment.

For this ,

Sort the segment according to first element and then check is this segment can be inside the the previous segment. By this approach you make minimum number of segment and that is your final answer.

For ex :

1 8

2 7

So if we can not reach (2 , 7) then definitely we can't reach (1 , 8) so here only one segment is consider that is (2 , 7). So answer is 1.

if another segment is (3 , 9) then this segment can't be inside the segment (1 , 7) so there is another segment which is (3 , 9). So answer is 2.

Let's take test case no 2:

1 8

2 7

3 5

4 6

7 9

(- - - - - - - -)

  (- - - - - -)

    (- - -)

      (- - -)

            (- - -)

So if we delete edge no. 5 then all the segments from 1 to 4 satisfied the condition that is they are not able to reach at his destination. So final answer is there are two segments (4 , 5) and(7,9). So answer is 2.

I shall provide some intuition.

Rather than think of it as a graph, it is much better to think of a straight line with N integer points.

We are given M segments and must delete the least number of lines so that all the end points of the M segments are disconnected.

Now, let us consider the end point with the smallest endpoint. Let it be S1 — [a1 b1]

Now, at least one line in between a1 and b1 has to be deleted so that S1 is disconnected.

However, which line to delete ?

We'd like to delete a line that lies in as many other segments as possible so that one deletion can disconnect as many segments as possible.

Let us delete the last line of the segment a1 b1.

We can see that this is optimal. Let us suppose that there is some other line which on deletion disconnects k segments. Since the segments are sorted by their end points — b, it ensures all the segments that are disconnected after deleting this line have their b >= b1. And if the start point a < line, then a < last_line.

So, we can always do at least as well by deleting the last line of a segment.

Thus, the greedy solution can be seen to be optimal.

So, we sort the segments based on the end points and delete the last edge of a segment only if the segment has no lines already deleted. For this, we keep track of the last line to be deleted.

    int no_of_deleted_bridges = 0, last_deleted = 0;
    for(int i = 1; i <= no_of_segments; i++)
    {
        if(segments[i].start > last_deleted)
        {
            last_deleted = segments[i].end - 1;
            no_of_deleted_bridges++;
        }
    }

Here is my complete code.