hotBoi's blog

By hotBoi, history, 2 months ago, In English

I recently came across a problem and I am unable to figure out the solution. The problem goes like this:

Lectures in an educational institution runs around the clock. There are n lectures and the schedule of the lectures is the same every day. The duration of lectures may vary from course to course. There are some lectures which spans across different days, for example, starting at 11 PM and ends at 1 AM the next day. Hence the earliest lecture or last lecture is not well defined.

The supervisor of the institution wants to check on every lecture in a day. For this, she makes a series of visits such that at the time of a visit, she checks on every lecture happening at that instant. In a day, there are m discrete times when the supervisor is free for visits. Also, in order to minimally disturb the lectures, it is advised that every lecture is checked exactly once. Give an algorithm that outputs the minimum number of visits the supervisor has to make so as to check on every lecture happening in a day exactly once, if that is possible.

I assumed a Dynamic Programming solution would be necessary, but I'm unable to figure out the exact recursive equation. Any help would be appreciated!.

Consider this more of an job interview problem and not a coding contest question.

  • Vote: I like it
  • -19
  • Vote: I do not like it