What´s the running-time of checking all orders?

Question

This algorithm should check for each order in the orderList, if there´s a free car of the ordered type in the carList.

An order contains a type of an car you wish to order as well as pickup and return time. Now I´m stuck to find out if this can run in O(nlog(n) + k) where k indicates the number of different car-types.

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

I did test my code and it seems to work just fine. I thought about using a hash-function over the car-types, so I only have to run through one smaller list (each list in my hash-table contains only cars of the same type). At least this is my idea.

Here´s the problem statement:

I do have k different car-types and n orders I need to check if all orders can be processed, meaning there´s no order unable to be performed. This can only be due to not having a car of the specified type free yet. An order contains as already said the desired car-type, pickup and return-time.

How would you solve this?

I assume that for each car-type exactly one car is available? Then the problem can be reformulated as: at any moment in time for each car-type there is at most one order for that car-type. — gogognome, May 26 '16 at 10:36
The order nlog(n) suggest that you sort something using quicksort or mergesort. What if you sorted the orders on start time? — gogognome, May 26 '16 at 10:37
I still need to run the whole order list even when sorted. Even when the orderList is sorted I need to run through the whole carList — Sartharon, May 26 '16 at 11:46

score 2 · Accepted Answer · edited May 23 '17 at 12:07

2

I would do it like this:

Bucket sort the orders by car type. O(n)
For the orders of each car type, find the maximum number of overlaps. O(n log(n) + k)
If the number found is greater than the number of cars for any type, return false (orders cannot be met). O(k)
return true (orders can be met). O(1)

Total complexity O(n log (n) + k)

edited May 23 '17 at 12:07

Community

1
1

answered May 26 '16 at 11:50

Klas Lindbäck

33,105
5
57
82

That sounds great! – gogognome May 26 '16 at 14:46
`check for each order` – greybeard May 26 '16 at 15:53
Where do you get the O(n log(n) + k) for me it seems like O(n log(n)) – Sartharon May 27 '16 at 09:07
There is a loop over the car types. This loop incurs a slight overhead that is proportional to the number of car types (`k`). – Klas Lindbäck May 27 '16 at 09:14

What´s the running-time of checking all orders?

1 Answers1