[Python] Interval scheduling ABC103D

ABC103D As shown in the figure below, the question is how many pieces are required to skewer everything. image.png 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:

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,

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)

Recommended Posts

[Python] Interval scheduling ABC103D
[Python] ABC175D
Interval scheduling learning memo ~ by python ~
[Python] DP ABC184D
[Python] UnionFind ABC177D
Ant book in python: page 43 Interval scheduling
Solve ABC168D in Python
Solve ABC167-D in Python
[Python] Cumulative sum ABC186D
[Python] Binary search ABC155D
Solve ABC159-D in Python
[Python] Dynamic programming ABC015D
[Python] Cumulative sum ABC179D
[Python] BFS (breadth-first search) ABC168D
ABC161D Lunlun Number with python3
[Python] DFS (Depth-first Search) ABC157D
Python
[Python] How to derive nCk (ABC156-D)
(Python) ABC162-D Consideration log and solution