0Pricing
Coding Interview Prep · レッスン

終了時刻が早い順のアクティビティ選択

重ならないイベントをできるだけ多くスケジュールします

「終了時刻が早い順のアクティビティ選択」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

スケジューリング問題

開始時刻と終了時刻を持つイベントが与えられたとき、アクティビティ選択では、どの2つも重ならないように、参加できるイベントの最大数を求めます。📅

重なりは競合を意味する

一方のアクティビティがもう一方の終了前に始まると、2つのアクティビティは競合します。重なる組からは1つのイベントしか選べません。

勝つためのルール

貪欲法の要点は、まだ選択可能なイベントの中から、常に最も早く終了するものを選ぶことです。早く終われば、後のイベントのための余地を最大限に残せます。

終了時刻でソートする

まず、すべてのアクティビティを終了時刻でソートします。すると、次に選ぶべき最善の候補は、条件に合う順番の次のイベントだけになります。

events.sort(key=lambda e: e[1])

最後の終了時刻を記録する

最後に選んだイベントの終了時刻を保持する変数を1つ用意します。新しいイベントは、両立するためにこの値以降に開始しなければなりません。

last_end = -1

走査して選ぶ

ソート済みのリストを1回走査します。イベントが 開始する時刻が last_end 以上なら選び、last_end をその終了時刻に更新します。

for s, f in events:
    if s >= last_end:
        count += 1
        last_end = f

n log n で実行する

計算量の大部分は O(n log n) のソートで、その後に線形時間の走査を1回行います。非常に大きな競技プログラミングの入力でも十分に高速です。

最も早い終了が勝つ理由

最初に終了するイベントは予定表の空きを最も早く作るため、より良い計画を妨げることはありません。どの最適なスケジュールに組み込んでも、同じように良い結果になります。

最も早い開始では失敗する

最も早い開始で選ぶと、1日全体を占有する長いイベントを選んでしまうことがあります。長さだけで判断しても誤るため、終了時刻を基準にしてください。

境界が接する場合に対応する

あるイベントが終了する時刻に別のイベントが開始する場合、それを競合とみなすかどうかを決めます。s >= last_end とすれば、連続するイベントを許可できます。

競技プログラミングでよくある形

このパターンは、部屋の予約、番組の視聴、ジョブの実行など、さまざまな問題に現れます。見抜くことができれば、最早終了ルールを適用できます。

クイックチェック

重ならないアクティビティを最大数選びたいとします。

まとめ

アクティビティを終了時刻でソートし、最後に選んだものが終了した時刻以降に開始するものを順に選びます。1回のソートと1回の走査で最大の集合を得られます。🚀

よくある質問

「終了時刻が早い順のアクティビティ選択」レッスンは無料ですか？

はい。「終了時刻が早い順のアクティビティ選択」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「終了時刻が早い順のアクティビティ選択」で何を学びますか？

重ならないイベントをできるだけ多くスケジュールします ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。

「終了時刻が早い順のアクティビティ選択」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 貪欲法の考え方
  2. 終了時刻が早い順のアクティビティ選択
  3. 比率による分割可能ナップサック
  4. 貪欲法が失敗する場合を見抜く
← Coding Interview Prepに戻る