gym scheduler #greedy (!"dynamic") #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——
(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. 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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s