開始位置で区間をソートする
処理の前にイベントを並べます
「開始位置で区間をソートする」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
区間とは何か
区間とは、[2, 5] のような開始値と終了値の 2 つの数の組です。区間問題の多くは、このような組のリストを扱います。📏
順序を付けると整理できる
区間は任意の順序で与えられるため、そのままでは考えにくいものです。最初にソートすると、左から右へきれいに走査できるようになります。
開始値でソートする
基本的には開始値でソートします。すると各区間は 1 つ前の区間と同じか、それより後から始まるため、1 回の走査で前へ進めます。
intervals.sort(key=lambda x: x[0])タプルは自然にソートされる
区間をタプルとして保存すると、Python は最初の要素、次に 2 番目の要素の順で自動的にソートします。ここでは key 関数さえ必要ありません。
intervals = [(3, 7), (1, 4), (2, 5)]
intervals.sort()開始値を先にする理由
開始値でソートすると、イベントを時間順に処理できます。次の区間は必ず後から始まるため、これは走査における重要な不変条件になります。
開始値が同じ場合
2 つの区間の開始値が同じ場合は、第 2 のキーによって順序が決まります。(start, end) でソートすると、短い区間が先になり、多くの場合に役立ちます。
intervals.sort(key=lambda x: (x[0], x[1]))終了値でソートする場合もある
最も多くのイベントを予定に入れる問題などでは、代わりに終了値でソートすることがあります。走査で知りたい情報に合うキーを選んでください。
intervals.sort(key=lambda x: x[1])ソートの計算量
ソートにはO(n log n)の時間がかかりますが、これは十分小さく、通常はこの種の問題の計算量の大部分を占めます。その後の走査は O(n) だけです。
追加データも一緒に保持する
各区間に ID や重みが付いている場合は、境界だけでなくレコード全体をソートします。キーが順序を決め、データはそのまま一緒に移動します。
intervals.sort(key=lambda iv: iv[0]) # iv = (start, end, id)ソートしてから走査する
ほぼすべての区間アルゴリズムは、まずソートしてから走査するという形です。順序を正しくすれば、マージ、個数計算、スケジューリングを単純なループで処理できます。
簡単なイメージ
区間をパーティーに到着する客だと考えてみてください。開始値でソートすると、客が到着する順に並ぶため、1 人ずつ迎えられます。
確認
これから区間のリストをマージしようとしています。
まとめ
区間は開始値と終了値の組であり、開始値でソートすると、乱雑なリストをきれいに走査できます。まずソートし、その後 O(n) で前方に処理します。🚀
よくある質問
「開始位置で区間をソートする」レッスンは無料ですか？
はい。「開始位置で区間をソートする」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「開始位置で区間をソートする」で何を学びますか？
処理の前にイベントを並べます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン1/4です。
「開始位置で区間をソートする」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- 開始位置で区間をソートする
- 重なり合う区間をマージする
- 最大重複数を求めるラインスイープ
- 重複をなくすための最小削除数