22

最近インタビューでこんな質問をされました。私はO ( n ² ) の解を思いつくことができましたが、インタビュアーはO ( n ) の解に夢中でした。私が理解したO ( n log n )の他のいくつかのソリューションもチェックしましたが、 O ( n ) ソリューションは、開始時間でソートされた予定を想定した私のお茶ではありません。

誰でもこれを説明できますか？

問題文: n件の予定が与えられています。各予定には、開始時刻と終了時刻が含まれています。競合するすべての予定を効率的に返す必要があります。

人物: 1,2, 3, 4, 5
アプリ開始: 2, 4, 29, 10, 22
アプリ終了: 5, 7, 34, 11, 36

答え: 2x1 5x3

O ( n log n ) アルゴリズム: 次のように開始点と終了点を分離します。

2s、4s、29s、10s、22s、5e、7e、34e、11e、36e

次に、このすべてのポイントを並べ替えます (簡単にするために、各ポイントが一意であると仮定します)。

2s、4s、5e、7e、10s、11e、22s、29s、34e、36e

終わりのない連続した開始がある場合、それは重複しています: 2 と 4 は隣接しているため、重複があります。

「s」のカウントを保持し、遭遇するたびに +1 し、e に遭遇するとカウントを 1 減らします。

4

5 に答える 5

19

この問題の一般的な解決策は、O ( n )では不可能です。

少なくとも、予定の開始時刻で並べ替える必要があります。これには、 O ( n log n ) が必要です。

リストがすでにソートされている場合、O ( n ) ソリューションがあります。このアルゴリズムは基本的に、次の予定が前の予定と重複しているかどうかを確認することを含みます。リストを実行するときに実際にはリストへの2つのポインターが必要なため、これには少し微妙な点があります。

  • 現在確認中の予定
  • これまでに遭遇した最も遅い終了時刻の予定 (以前の予定ではない可能性があります)

並べ替えられていないケースのO ( n ) ソリューションは、他の制約がある場合にのみ存在できます。たとえば、予定のタイムスロットの固定数などです。この場合、HashSets を使用して、各タイムスロットをカバーする予定を決定できます。アルゴリズムは、おおまかに次のようになります。

  • タイムスロットごとに HashSet を作成する - O (1) タイムスロット番号は固定定数であるため
  • 予定ごとに、その ID 番号を、対象となるスロットの HashSets に格納します - O ( n )。一定数のタイムスロットを更新すると、予定ごとにO (1) になるためです。
  • スロットを実行し、オーバーラップをチェックします - O (1) (オーバーラップする予定を繰り返し処理して結果として返す場合はO ( n ))
于 2012-09-19T03:54:00.310 に答える
5

開始時間と終了時間、およびスケジューリングを行う際の解像度に何らかの制約があると仮定すると、各予定を使用する/使用しない時間のビットマップに変換して実行するのはかなり簡単に思えます。使用中のスロットでのカウンティング ソート (バケット ソートとも呼ばれます)。どちらも線形であるため、結果は線形であるはずです (私の考えが正しければ、予定の数ではなくタイムスロットの数で線形になるはずです)。

少なくとも面接の質問としてこれを尋ねた場合、私が主に期待することは、候補者がそれらの制約 (つまり、それらの制約が許可されているかどうか) について尋ねることです。今から 1000 年後の予定をスケジュールしたり、1 分 (ナノ秒のようなものは言うまでもありません) の精度でスケジュールしたりすることが非現実的であることを考えると、それらは合理的な制約のように思えますが、それらを想定する前に質問する必要があります。

于 2012-09-05T14:42:48.527 に答える
2

単純なアプローチは、2 つの並列ツリーを構築することです。一方は各間隔の開始点で並べ替えられ、もう一方は終了点で並べ替えられます。これにより、O(log n) 時間で各ツリーの半分を破棄できますが、結果をマージする必要があり、O(n) 時間がかかります。これにより、O(n + log n) = O(n) のクエリが得られます。

于 2012-09-05T20:40:19.883 に答える
1

提供されたデータに応じて、O(n log (n)) 時間未満で間隔を見つけることができる間隔ツリーと呼ばれるデータ構造に出会いました。

于 2012-09-20T19:04:18.163 に答える
1

これは、恐ろしい疑似コードで、私が考えることができる最高のものです。問題をできるだけ減らしてみました。これは On^2 よりも小さいだけです (と思います)。

最後の出力には、特定のアポイントがそのアポイントの特定の出力行で競合するすべてのアポイントが表示されるわけではありませんが、ある時点ですべての競合が表示されることに注意してください。

また、予定の名前を開始時間順に数値的に変更したことにも注意してください。

output would be something like the following:

Appointment 1 conflicts with 2
Appointment 2 conflicts with
Appointment 3 conflicts with
Appointment 4 conflicts with 5
Appointment 5 conflicts with


appt{1},appt{2},appt{3} ,appt{4} ,appt{5}
  2      4       10       22      29
  5      7       11       36      34

疑似コード

list=(1,2,3,4,5)
for (i=1,i<=5,i++)
    list.shift()   **removes first element
    appt{i}.conflictswith()=list

for (i=1,i<=n,i++)
{   number=n
    done=false
    while(done=false)
        {if (number>i)
            {if (appt(i).endtime() < appt(number).startime())
                {appt{i}.conflictswith().pop()}
             else
                {done=true}
             number--
             }
        else
            {done=true}
        }
}
for (i=1,i<=n,i++)
    print "Appointment ",i," conflicts with:",appt{i}.conflictswith()
于 2012-09-05T15:47:10.990 に答える