Lynbrook Computer Science

Happy Halloween! Today we went over greedy algorithms and when and when not to use them. We also went over two solutions to the previous Problem of the Week and introduced the new Problem of the Week. The new PotW is as follows:

• It’s Monday, and Halloween, so naturally, the cows are out partying. Bessie has a list of N<100,000 parties and their start/end times (in 24 hr format), and she wants to maximize the number of parties she attends, k. She must attend the entirety of each party.
• Note that the parties are sorted by end time (VERY important).

Sample Input:
4
0:00 0:05
0:00 0:10
0:05 0:15
0:15 0:20
Sample Output: (print out k on a single line)
3

• This is worth 20 pts, but for 15 extra pts, print out on a second line the maximum amount of time she can spend attending k parties (fairly difficult).

To learn how to apply a greedy algorithm to the problem of the week, check out the meeting slides. As a hint for the extension, you can use dynamic programming and binary search – don’t worry if you can’t solve it though, it’s designed as a tiebreaker.