Most Events You Can Attend
Problem
A conference lists events as [startDay, endDay], inclusive. You can attend an event on any single day within its range, and you can attend at most one event per day. Return the largest number of events you can attend.
Examples
Input: events = [[1, 2], [2, 3], [3, 4], [1, 2]]
Output: 4
Why: days 1 and 2 go to the two [1, 2] events, then [2, 3] on day 3 and [3, 4] on day 4Input: events = [[1, 4], [4, 4], [2, 2], [3, 4], [1, 1]]
Output: 4Input: events = [[1, 1], [1, 1], [1, 1]]
Output: 1
Why: edge case, three events compete for the same single dayHints
0 / 3
Go through the days in order. On a given day, several open events could be attended. Which one is the safest to use today?
Pick the open event that ends soonest. Any other choice can be swapped for it without losing an event, because the one ending soonest has the least time left to be attended later.
Sort events by start day. Walk the days, pushing the end day of every event that has started into a min-heap, throwing away heap entries that have already ended, and attending the event at the top of the heap. When the heap is empty, jump straight to the next start day.
Solution
On each day, the right event to attend is the open one with the earliest end: if an optimal plan attended something else today, swapping in the earliest-ending event keeps the plan valid, because that event could only have been attended on days that the other one also covers. A min-heap of end days holds the events that have started, so the earliest end is always on top, and expired events are discarded as they surface. Sorting by start day lets the walk add events as their first day arrives and skip idle stretches of days entirely. Each event is pushed and popped once, so time is O(n log n) and space is O(n).
import heapq
def most_events(events):
events = sorted(events)
ends, i, n, day, attended = [], 0, len(events), 0, 0
while i < n or ends:
if not ends:
day = max(day, events[i][0]) # skip idle days
while i < n and events[i][0] <= day:
heapq.heappush(ends, events[i][1]); i += 1
while ends and ends[0] < day: # already over
heapq.heappop(ends)
if ends:
heapq.heappop(ends) # attend the one ending soonest
attended += 1; day += 1
return attended
print(most_events([[1, 2], [2, 3], [3, 4], [1, 2]])) # -> 4
print(most_events([[1, 4], [4, 4], [2, 2], [3, 4], [1, 1]])) # -> 4
print(most_events([[1, 1], [1, 1], [1, 1]])) # -> 1Stuck on the idea rather than the code? Huffman Intuition covers it.