データ構造の中で最大の最小値と最大のキーの値を見つける

Question

膨大な数のタスクを格納するシステムを持っています。各タスクには、以下のパラメータがあります。

Time t  
Priority p  

すべてのタスクは、ユニークな時間を持っています。これは、2つのタスクが同じTimeパラメーターを持つことができないことを意味します。
ただし、優先度は一意ではありません。複数のタスクは同じ優先順位を持つことができます。

4種類のクエリに対処できるシステムを設計する必要があります。それぞれのタイプの問合せの可能性も同じです。次のクエリの種類があります：

1. UpdateTask（T、P）
   このクエリは、優先順位pまでの時間tでタスクの優先順位を設定するためのシステムを望んでいます。タスクがシステムに存在しない場合は、新しいタスクが作成されます。タスクが存在する場合、タスクの優先順位が更新されます。

2. DeleteTask
   このクエリは、システムが時刻tに関連付けられているタスクを削除することを要求します。そのようなタスクがシステムに存在しない場合、何もする必要はありません。

3. GetMaximumPriority（）とGetMinimumPriority（）
   このクエリはシステムで利用可能なタスクの最低優先順位と最高優先順位を印刷するシステムを望んでいます。

4. GetPriorityofTaskAtMaximumTime（）
   このクエリは、パラメータt（時間）の最大値を持つタスク

の優先順位を印刷するシステムを望んでいる私は、このシステムのためのデータ構造を設計する必要がありますこれらのデータ構造のアルゴリズムを実装します。私はこれをJavaで実装する必要があります。

私のアプローチ：Key as TimeとValueを優先度としてHashMapを作成しました。 HashMapを使用すると、最初の2つのクエリを一定の時間内に処理できます。しかし、最後の2つのクエリは、O(n)という時間の複雑さを持っています。

質問：この問題の効率的でスペース効率の良いデータ構造とアルゴリズムがありますか？私は主にこれを解決するアプローチが必要です。完全に実装されたコードは必要ありません。ありがとう。

Answer 1

可能な方法の1つは時間と優先度の2つのインデックスを維持することです。一定の時間を持つ2つのバランスのとれた検索ツリーを操作しましょう。firstKey()/lastKey()操作。 TreeMapのインターフェイスを使用しますが、これはC++のstd::mapに似た実装でなければなりません（更新時にイテレータを最初と最後の要素に維持するだけです）。

最初のマップはMap<Time, Priority> tasks、次はMap<Priority, Integer> prioritiesです。既存の各優先度値に対する第2のマップは、この優先度値を有するタスクの数を記憶する。したがって、4番目のクエリには、3番目のクエリにはprioritiesを使用できます。

1. UpdateTask（T、P）

   Priority oldp = tasks.put(t, p); 
   if (oldp != null) { 
       decreasePriority(oldp);  
   } 
   increasePriority(p); 
   

   複雑：O（Nログ（））
   
   

2. DeleteTask（T）

   if (tasks.containsKey(t)) { 
       Priority oldp = tasks.get(t); 
       tasks.remove(t); 
       decreasePriority(oldp); 
   } 
   

   複雑：O（ログ（N））
   
   

3. GetMaximumPriority（）、GetMinimumPriority（）

   return priorities.lastKey(); 
   
   return priorities.firstKey();  
   

   複雑：O（1）（と適切lastKey()/firstKey()実施、O(log(n))とjava.util.TreeMap）。
   
   

4. GetPriorityofTaskAtMaximumTime（）

   return tasks.lastEntry().getValue(); 
   

   複雑：O（1）

---

（ java.util.TreeMapと適切 lastEntry()実装 O(log(n))と）

この結果、操作で線形の複雑さが回避されます。

Answer 2

一般的な考え方 - あなたのデータ型に基づいて変更される可能性があります。私はあなたの時間と優先度のキーとしてタイプのマップデータ型を持つことができると思います。データを削除したい場合は、時間をキーにしてそのマップを検索して削除し、同様に時間をキーとして更新することができます。

次に、それぞれの時間と優先度のリストを1つずつ作成し、必要に応じてリストを並べ替えることができます。

Answer 3

hereと書かれているように、O（1）でminとmaxを見つけることができるHeapまたはPriorityQueueを試すことができます。
また、O（log n）のminとmaxを削除して抽出しますが、検索はO（n）にとどまります。 タスククラスにComparatorを実装する必要があります...