Какова продолжительность проверки всех заказов?

Question

Этот алгоритм должен проверять каждый заказ в orderList, если в carList есть свободная машина с упорядоченным типом.

В заказе указан тип автомобиля, который вы хотите заказать, а также время получения и возврата. Теперь я застрял, чтобы узнать, может ли это работать в 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 проблема заявление:

У меня есть к различным автомобилям-тип и п заказы мне нужно, чтобы проверить, все заказы могут быть обработаны, смысл 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 журнал (п) + к)