Puzzle 2: The Best Time to Party

MIT 6.S095 Programming for the Puzzled, IAP 2018
Instructor: Srini Devadas

Ever wanted to go to a party at just the right time so you can hang out with all the cool people? Prof. Devadas describes an efficient, algorithmic way of finding this time and explains how you can write a program that computes the best time.

License: Creative Commons BY-NC-SA

[romanoadler]

this is an awesome course for everyone learning how to write more performant code

[RationalSphere]

If the granularity of arrival/departure times is shorter than the interval you attend the party, there's a subtlety. Say intervals (6:00, 11:00) (6:00, 8:10) (8:30, 11:00), then arriving at 7:50 and leaving 8:50 gives you some time with 3 celebrities, even though 7:50 is not a celebrity-arrival time, and celebrity-occupancy never reaches 3. (If you spoof that the celebrities arrive earlier, by the amount of time you attend the party, the algorithm should account for this. - Except, if the best time is really early, this will tell you to arrive before the party starts...)

[ali]

no matter how I think of it, the code at 13:45 is wrong, and there should be "or" instead of "and" at the loop where check celebrity is in the range time, because if she was already in, she is counted, and if she was going to go out within that time as well, she is also counted, so I can't understand why there is an AND instead of OR

[rr_kundan]

We can just store the frequency of time and just return the time with max frequency right?

[bhanunadar]

Do we need to sort? Can we do this in O(N) where N will be total celebrity. After finding the start point and end point. We can iterate the schedule and update as for every entry as +1 and exit as - 1. That is if a celebrity enters at 6 and exit at 7. We update arr[6] +=1 and arr[7] - =1
In the send just keep on iterate this array and adding the values, maximum sum at any point will be the answer

[vamsikrishnagannamaneni]

sorted_times = sorted(times_unsorted, key=lambda x: (x[0], x[1] == 'start'))
will this have a better time complexity tha O(n^2) ?

[MaheshGaikwadCSB]

max(celebrity_list, key= celebrity_list.count)

python inbuilt

[saringsadiqueali]

MIT buy erase friendly boards please :p

[dollarbar]

can someone define chooseTime(). My code won't compile without it.

[carlosgarza]

I keep thinking this can be done in better then O(n^2). Any ideas?

[strawberryblueberry]

Lol the eraser is so bad, MIT and can't even afford modern day technology?