1

問題の説明は次のとおりです。

特定の日 d には、開始時刻と期間を持つ n 個のイベントがあります。例：

e1 10:15:06 11ms (ms = milli seconds)
e2 10:16:07 12ms
......

時間 x と n を調べる必要があります。x は、最大のイベントが実行された時間です。

私が考えている解決策は 、d日目にすべてのミリ秒をスキャンすることです。しかし、その要求の合計は 86400000*n の計算です。例

Check at 00::00::00::001 How many events are running
Check at 00::00::00::002 How many events are running
Take max of Range(00::00::00::01,00::00::00::00)

私が考えている2番目の解決策は次のとおりです。

For eventi in all events
   Set running_event=1
   eventj in all events Where eventj!=eventi
        if eventj.start_time in Range (eventi.start_time,eventi.execution_time)
           running_event++

そして、running_event の最大値を取得します

これに対するより良い解決策はありますか？

4

2 に答える 2

2

O(n log n)これは時間内に解決できます。

  • すべてのイベントの配列を作成します。この配列はすでに部分的にソートされています:O(n)
  • 配列を並べ替える: O(n log n); あなたのライブラリは部分的なソートを利用できるはずです（timSortはそれを非常にうまく行います）。期待される実行時間を改善するため に、分布ベースのソートアルゴリズムを調べてください。
    • イベント境界を境界時間で昇順に並べ替えます
    • 接触間隔が重複していないと見なされる場合、並べ替えイベントは並べ替えの開始前に終了します (接触間隔が重複していると見なされる場合、並べ替えイベントは並べ替えの開始後に終了します)
  • 初期化running= 0、running_best= 0、best_at= 0
  • イベント境界ごとに:
    • イベントの開始の場合は、インクリメントしますrunning
    • の場合running > running_best、設定best_at= 現在のイベント時間
    • イベントの終了の場合はデクリメントrunning
  • 出力best_at
于 2012-12-23T07:59:00.870 に答える
0

からまでI続く各間隔(タスク) について、すべての間隔の終わりのみをチェックすることで、チェックするポイントの数を減らすことができます。排他的である場合は、チェックしてください。t1t2t1t2t1t2t1-EPSILON, t1+EPSILON, t2-EPSILON, T2+EPSILON

これらのケースがカバーしていない以上のものを得ることができないことは簡単にわかります (理由を自分で納得させてください)。

例：

tasks run in `[0.5,1.5],[0,1.2],[1,3]`
candidates: 0,0.5,1,1.2,1.5,3
0 -> 1 tasks
0.5 -> 2 tasks
1 -> 3 tasks
1.2 -> 3 tasks (assuming inclusive, end of interval)
1.5 -> 2 tasks (assuming inclusive, end of interval)
3 -> 1 task (assuming inclusive, end of interval)
于 2012-12-23T07:58:34.863 に答える