gym scheduler #greedy#Junli

I find this algorithm extremely simple but not easy to recognize. The extreme simplicity indicates some important/valuable tip but not sure what.

Write a scheduler for a single gym equipment(like a room). Every morning at 8am before start of day, we receive a batch file containing all booking requests for that day. We run the scheduler once, and all accepted bookings are confirmed and finalized. Each request is identified by a pair of start/end times on the current day. No 2 requests share the same start/end times (perhaps because the duplicates are already filtered out). Exercise duration is in blocks of 1 minute. We earn $1 rental for each session regardless of duration.  Optimization goal is to allocate as many sessions as possible. We don’t care idle time; it doesn’t cost us. Let’s say the candidate for the “optimal” allocation plan is PlanK.
—–solution——
Pick the booking that ends earliest. Alternatively, pick the booking that starts later than all others.
(I feel this is not a dynamic programming algorithm, but a greedy algorithm.)

If there’s a last-minute user (4.59pm – 5pm, let’s call it AA), then it’s always good to accept. This last minute user AA doesn’t block others. AA is a minimum-hindrance session.

If PlanK ends with any other session (call it BB), BB surely starts before 4.59pm. BB is a bigger hindrance than AA is. If we replace BB with the last-minute user AA, we would produce a “safer” plan – PlanL. PlanL is at least as optimal as PlanK, and can potentially /accommodate/ additional sessions. Therefore PlanK without AA isn’t the optimal. The optimal plan ought to include the last-minute allocation.

That’s the key to the optimization. The last-to-begin session has minimum hindrance and should always be selected. After that selection, eliminate all requests that are now hindered. Then among the remaining  requests, look for the last-to-begin.

———-
Exploiting symmetry, you can reverse the algorithm by picking the first-to-end session.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s