Resource scheduling problem

Question

I'm developing a motorcycle hire website. The problem I have is how to solve the problem of assignment a guest to a motorcycle in an efficient way. I know how to do it in a "silly" way, but I want to know if there is a classical algorithm that solves this kind of problem. It's the same problem as the assignment of a guest to rooms in a hotel. In this last example, the goal is to achive maximum occupancy by never rejecting a reservation due to inefficient scheduling.

I'm pretty sure that this problem has to be a classic problem that has a known solution.

Thanks a lot.

Answer 1

What you're interested in is called Interval Scheduling. Assuming all reservations have the same weight (none are favored over any other), you'd want a greedy algorithm.

Here (pdf) are some good slides about the topic.

Basically, you want to schedule the earliest-ending reservations first.

Answer 2

This is Interval scheduling but it's an online algorithm. If you want to read further you can read here:

http://www-bcf.usc.edu/~dkempe/teaching/online.pdf