interval scheduling
date: 2021-04-24 excerpt: 区間スケジューリングについて
区間スケジューリング(interval scheduling)について
- 貪欲法でよくある例題の一つにある
- 開始時間と終了時間が定義されている時、最大の実行数を求める時
- 終了日でソートして終了日が早い順にピックアップするのが最適解
具体例
N = int(input())
BA = []
for i in range(N):
a, b = map(int, input().split())
BA.append([b,a])
BA = sorted(BA)
ans = 0
last = 0
for b, a in BA:
if last < a:
ans += 1
last = b
print(ans)