An Activity Selection Problem

There is a very interesting problem I recently came across as part of Google’s foobar challenge. The problem is called ‘zombie antidote’.

I wanted to write down some thoughts as I made my way towards solving this problem.


  • The problem smells like Dynamic Programming.
  • However, there are some challenges in coming up with the DP solution
    • How to build up the optimal substructure (aka. recurrence relation) for the problem ?
    • How to show overlapping subproblem property ?
  • It is useful to look at problems from different perspectives.
    • E.g. Can the activity selection problem be formulated as a Graph theory problem ?


  • Refresh basics of Dynamic Programming Algos.
    • Especially useful here was understanding the cut-rod problem from Cormen’s algo book
  • Understanding the relationship between the following 3 fundamental algorithmic approaches.
    • Dynamic Programming
    • Greedy Algorithms
    • Graph Theory
  • As it turns out, the activity selection problem can indeed be formulated in all of the 3 algo approaches listed above.




Leave a Reply

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

You are commenting using your 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