すべての注文をチェックする実行時間はどのくらいですか？

Question

このアルゴリズムは、carListに順序付けされた型のフリーカーがあるかどうか、orderListの各注文をチェックする必要があります。

ご注文には、ご希望の車種と、ピックアップおよび返品時間が含まれています。今、私はこれがO(nlog(n) + k)で実行できるかどうか調べるために立ち往生しています。ここで、kは異なる車種の数を示します。

public static boolean CheckAllOrder(List orderList, List carList) { 
    int count = 0; 
    for (int i = 0; i < orderList.size(); i++) { 
     int type = orderList.get(i).type; 
     long start = orderList.get(i).start; 
     long end = orderList.get(i).end; 
     for (int j = 0; j < carList.size(); j++) { 
      Car currentCar = carList.get(j); 
      if (currentCar.type == type) { 
       if (currentCar.occTil == 0 && currentCar.occSince == 0) { 
        currentCar.occSince = start; 
        currentCar.occTil = end; 
        count++; 
        break; 
       } else if (currentCar.occTil < start) { 
        currentCar.occTil = end; 
        count++; 
        break; 
       } else if (currentCar.occSince > end) { 
        currentCar.occSince = start; 
        count++; 
        break; 
       } 
      } 
     } 
    } 
    if (count == orderList.size()) { 
     return true; 
    } else { 
     return false; 
    } 
} 

私は自分のコードをテストしなかったし、それだけで正常に動作するようです。 私は車のタイプについてハッシュ関数を使うことを考えました。したがって、私はハッシュテーブルの各リストに同じタイプの車しか入っていない小さなリストを1つ走らせるだけです。少なくともこれは私の考えです。

Here's問題声明：私はすべての注文を処理できるかどうかを確認する必要がk個の異なる車のタイプとn注文 を持っています

は、順不同できない意味there'sを行うことができます。これは、指定されたタイプの車がまだ無料になっていないことが原因です。注文には、すでに述べたように、希望する車種、ピックアップ、および戻り時間が含まれています。

どうすれば解決できますか？

Answer 1

私はこのようにそれを行うだろう：

1. バケットは、車の種類によってソート順。 O（n）

2. 各車種のオーダーについてはfind the maximum number of overlapsです。 O（n log（n）+ k）

3. 見つかった数がどのタイプの車の数よりも多い場合は、false（注文に一致しない）を返します。 O（k）

4. 返信true（注文が満たされる）。 O（1）

総複雑性はO（n N（ログ）+ K）