Activity Selection Problem
アクティビティ i は時刻 start[i] から時刻 finish[i] まで行われます。1人が同時に行えるアクティビティは1つで、次のアクティビティは前のアクティビティが終了した後に開始しなければなりません。別のアクティビティが終了する時刻ちょうどに開始するアクティビティを、その後に行うことはできません。
1人が行えるアクティビティの最大数を返してください。
関数
- startinteger-array
- 各アクティビティの開始時刻
- finishinteger-array
- 各アクティビティの終了時刻。finish[i] は start[i] に対応します
- 戻り値integer
- 一人が次々にできるアクティビティの最大数
制約
1 ≤ start.length == finish.length ≤ 50000 ≤ start[i] ≤ finish[i] ≤ 105- アクティビティは同時に開始および終了することがあります。配列はソートされていません。
例
- 入力
- start = [10, 12, 20, 14, 25, 21]finish = [13, 16, 24, 19, 30, 22]
- 出力
- 4
- 説明
- 10から13、14から19、21から22、25から30を行うと4になります。5は不可能です。10から13は12から16と重なり、21から22は20から24と重なるためです。
- 入力
- start = [1, 5, 9]finish = [5, 9, 12]
- 出力
- 2
- 説明
- 5から9までのアクティビティは、最初のアクティビティが終了する時刻ちょうどに始まるため、その後に続けることはできません。1から5まで行い、その後9から12まで行うことは可能なので、答えは
2です。
- 入力
- start = [0, 2, 5, 8]finish = [100, 4, 7, 10]
- 出力
- 3
- 説明
- 0から100までのアクティビティは、ほかのすべてと重なっています。それを除くと、2から4、5から7、8から10は順番に並びます：
3。
発展問題
今では2人が並行して作業し、それぞれ一度に1つの作業を行います。2人で一緒にいくつの作業をこなせますか？それぞれの作業は誰が担当すべきですか？
ヒント
1つずつ開いてください。開くたびに少しずつ答えに近づきます。
どの活動を最初に行うかは、すでに決まっているとします。その後にできるだけ多くの時間を残すには、どの活動を最初に行いたいですか？
最も早く終了するアクティビティを最初に選ぶのが常に安全です。他のどのアクティビティから始める計画でも、それを最も早く終了するアクティビティと入れ替えて、同じ数のアクティビティを選べます。その後、それが終了した後に開始するアクティビティについて、同じ問いを繰り返します。
終了時刻でアクティビティを並べ替え、それぞれの開始時刻も終了時刻と一緒に移動します。最後に選んだアクティビティの終了時刻を保持しながら、並べ替えたリストを順に見ていき、その時刻より開始時刻が厳密に大きいアクティビティをすべて選びます。
解説
アクティビティのすべての部分集合を試すには、指数時間がかかります。代わりに、1つの貪欲なルールで問題を解決できます。まだ予定に収まるアクティビティの中から、常に最も早く終了するものを選びます。終了時刻で並べ替えると、このルールを1回の走査で実行できます。
最も早く終わるものを、何度も選びましょう
正しいが、最大のテストでは終わらない
考え方
最も早く終わるアクティビティは、最初に選ぶものとして、他のどのアクティビティにも少なくとも劣りません。それより遅く終わることはないため、他のアクティビティを最初に選んだ場合にその後に続けられるアクティビティは、これを選んだ場合にも続けられます。また、これに入れ替えても選べる数は変わりません。このアクティビティを選んだ後は、終了時刻より後に開始するアクティビティについて、同じ問題を繰り返します。
最初の例では、10 から 13 を選び、次に 14 から 19、次に 21 から 22、そして 25 から 30 を選びます。合計4つです。
選ぶたびに、すべてのn個のアクティビティを調べるため、計算量は答えの数にnを掛けたものです。5000個のアクティビティがすべて順番に収まる場合、チェック回数は2500万回になります。
アルゴリズム
- すべての開始時刻より小さくなるように、
count = 0とlastFinish = -1を設定します。 start[i] > lastFinishを満たし、最も早く終了するアクティビティをすべてのアクティビティから探します。- 該当するものがなければ、
countを返します。 - それ以外の場合は、
countに 1 を加え、lastFinishをそのアクティビティの終了時刻に設定して、再び探します。
def maxActivities(start, finish):
n = len(start)
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
while True:
# among the activities that start after last_finish, find the one that ends first
pick = -1
for i in range(n):
if start[i] > last_finish and (pick == -1 or finish[i] < finish[pick]):
pick = i
if pick == -1:
return count
count += 1
last_finish = finish[pick]終了時刻で並べ替え、貪欲に選ぶ
考え方
終了時刻で一度ソートすれば、上のスキャンで探索した順にアクティビティを確認できます。ソート済みのリストをたどりながら、最後に選んだアクティビティの終了時刻であるlastFinishを保持します。start[i] > lastFinishを満たすアクティビティは、まだ選択可能なものの中で最も早く終了するため、選びます。それ以外は最後に選んだアクティビティと衝突するので、スキップしても問題ありません。
ソートすると、最初の例は10〜13、12〜16、14〜19、21〜22、20〜24、25〜30の順になります。最初、3番目、4番目、6番目を選びます。12は13より後ではなく、20は22より後ではないためです。
終了時刻が同じ場合の規則は必要ありません。tに終了するアクティビティを選ぶと、同じくtに終了する他のアクティビティはすべて、開始時刻がt以前なのでスキップされます。
アルゴリズム
- 各アクティビティを
finishで並べ替え、各開始時刻も対応する終了時刻と一緒に移動します。 count = 0とlastFinish = -1を設定します。- その順序で各アクティビティについて、
start[i] > lastFinishの場合、countに1を加え、lastFinish = finish[i]を設定します。 countを返します。
def maxActivities(start, finish):
order = sorted(range(len(start)), key=lambda i: finish[i]) # earliest finish first
count = 0
last_finish = -1 # nothing taken yet; every start is at least 0
for i in order:
if start[i] > last_finish:
count += 1
last_finish = finish[i]
return count
落とし穴と境界ケース
- 開始時刻で並べ替えること。3つ目の例では、0から100までの活動が最初に始まり、残りの3つを妨げます。
- 最も短い活動を最初に選ぶこと。1から5、5から6、6から10の場合、最も短いのは5から6で、ほかの2つの活動の両方と重なります。1から5と6から10を選ぶと、2つになります。
≥ではなく>を使って比較すること。2つ目の例では、2ではなく3が返されます。finishだけを並べ替えること。各開始時刻は対応する終了時刻と一緒に移動させる必要があります。そうしないと、開始時刻と誤った活動が組み合わされます。lastFinishを0に設定して始めること。すると、0から1までの活動が1つだけの場合、0 > 0は偽なので、その活動はスキップされます。
よくある質問3
活動選択問題の時間計算量はどのくらいですか？
終了時刻による並べ替えには O(n log n) のコストがかかり、その後の貪欲な走査は O(n) なので、並べ替えが支配的です。アクティビティがすでに終了時刻順に並んでいる場合は、走査だけで O(n) 時間、O(1) の追加領域で解決できます。
N個の会議を1つの部屋で行う問題とは何ですか？
会議を使って説明した同じ問題です。1つの部屋にN件の会議があり、会議は前の会議が終了した後にしか開始できません。会議を終了時刻順に並べ、最後に選んだ会議が終了した後に開始する会議をそれぞれ選びます。会議の一覧を作るには、選んだ会議のインデックスを記録し、終了時刻が同じ場合はインデックスが小さい方を優先します。
アクティビティ選択問題は動的計画法ですか？
そうなることもありますが、必ずしもそうである必要はありません。終了時刻順に並べた活動について、それぞれの活動で終わる活動の最大数を保持する表を使えば、O(n²)で答えを求められます。貪欲な選択は常に安全なので、1回の走査で十分です。活動に値が付いていて、その合計を最大化する場合は、この表が適切な手段になります。
似た問題
同じ考え方を使う問題です。2〜3問解くとパターンが身につきます。
def maxActivities(start, finish):
# ここにコードを書いてくださいテスト #1
テスト #2
テスト #3
引数
start = [10, 12, 20, 14, 25, 21] finish = [13, 16, 24, 19, 30, 22]
期待される出力
4