檢查所有訂單的運行時間是什麼？

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; 
    } 
} 

我測試了我的代碼，它似乎工作得很好。 我想過在汽車類型上使用散列函數，所以我只需要運行一個較小的列表（我的散列表中的每個列表只包含相同類型的汽車）。至少這是我的想法。

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. return true（可以滿足訂單）。 O（1）

總複雜度爲O（N日誌（N）+ K）