0Pricing
Coding Interview Prep · レッスン

開始位置で区間をソートする

処理の前にイベントを並べます

「開始位置で区間をソートする」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン1/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全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チューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「開始位置で区間をソートする」で何を学びますか？

処理の前にイベントを並べます ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

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

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

「開始位置で区間をソートする」レッスンにはどのくらい時間がかかりますか？

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

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

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

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

  1. 開始位置で区間をソートする
  2. 重なり合う区間をマージする
  3. 最大重複数を求めるラインスイープ
  4. 重複をなくすための最小削除数
← Coding Interview Prepに戻る