[Python] Interval scheduling ABC103D

ABC103D As shown in the figure below, the question is how many pieces are required to skewer everything. The interval scheduling problem is as follows:

Given M intervals, choose the maximum number of intervals so that no two intervals share a time zone

It's a well-known problem at the beginning of the Greedy chapter of the ant book, and you can sort it at the end of the section and take it to Greedy.

In fact, the answer to this question is the same as the optimal solution for the interval scheduling problem:

• First, if the answer to the interval scheduling problem is k, then k do not share a time zone, so at least k skewers are required to stab them all (** weak duality **).

On the contrary, the fact that k skewers are sufficient can be understood by carefully following the movement of the greedy algorithm for the interval scheduling problem. In particular,

• If you skewer k sections selected in the interval scheduling problem from the right end, you can skewer all sections with just k skewers (** strong duality **)

Sample code

from operator import itemgetter

n, m = map(int, input().split())

#Sort at the end of the interval
ab = sorted([tuple(map(int, input().split())) for i in range(m)], key=itemgetter(1))
#The bridge that was removed last time
removed = -1
ans = 0

for a, b in ab:
    #a is greater than removed=I haven't removed it yet
    if a > removed:
        removed = b - 1
        ans += 1

print(ans)