One Event Per Day
MediumIntervals
Problem
A festival lists events; event i is [firstDay, lastDay] and can be attended on any single day in that range (both ends included). A visitor can attend at most one event per day.
Return the maximum number of events the visitor can attend.
Example 1
- Input:
- events = [[1, 2], [2, 3], [3, 4]]
- Output:
- 3
Attend them on days 1, 2 and 3.
Example 2
- Input:
- events = [[1, 2], [2, 3], [3, 4], [1, 2]]
- Output:
- 4
Days 1 and 2 for the two [1, 2] events, day 3 for [2, 3], day 4 for [3, 4].
Constraints
- 1 ≤ events.length ≤ 10^5
- 1 ≤ firstDay ≤ lastDay ≤ 10^5
Hint
Show the first hint
On a given day, several events may be available. Which one should you attend?
Walkthrough
How to approach it
01Clarify before coding
- Does attending take the whole day? Yes, one event per day.
- Must an event be attended on consecutive days? No, a single day inside its range is enough.
- How many days can there be? Up to 10^5, so sweeping day by day is affordable.
02Brute force
Try every assignment of events to days (bipartite matching).
Cost: Matching is polynomial but heavy, O(E·√V) with up to 10^10 edges here; far beyond what is needed.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.