クルトンのプログラミング教室

Pythonの使い方やPythonを使った競技プログラミングの解法などを解説しています。

Pythonで理解する蟻本「2-2 区間スケジューリング問題」(p.43)

この記事は「プログラミングコンテストチャレンジブック第2版」(蟻本)の
「2-2 区間スケジューリング問題」(p.43)
のコードをPythonで書き直したものとなっています。

入力

n\\s_{1}\,s_{2}\,…\,s_{n}\\t_{1}\,t_{2}\,…\,t_{n}

入力例



5
1 2 4 6 8
3 5 7 9 10


解答

MAX_N = 100000

# 入力
N = int(input())
S = list(map(int,input().split()))
T = list(map(int,input().split()))

# 仕事をソートするための配列itv
itv = []

# 終了時間の早い順にしたいため、Tを配列の一つ目に、Sを二つ目に入れる
for i in range(N):
    itv.append([T[i], S[i]])
itv.sort()

# tは最後に選んだ仕事の終了時間
ans = 0
t = 0
for i in range(N):
    if t < itv[i][1]:
        ans += 1
        t = itv[i][0]
print(ans)