Leetcode 1353: Maximum Number of Events That Can Be Attended
You are given a list of events where each event is represented by a pair [startDay, endDay]. Your task is to find the maximum number of events you can attend, ensuring that you attend only one event per day.
Problem
Approach
Steps
Complexity
Input: The input consists of a list of events, where each event is represented by a pair of integers indicating the start and end day of the event.
Example: For example, [[1, 2], [2, 3], [3, 4]] where each pair represents an event that lasts from start to end day.
Constraints:
• 1 <= events.length <= 10^5
• events[i].length == 2
• 1 <= startDay[i] <= endDay[i] <= 10^5
Output: The output should be a single integer representing the maximum number of events you can attend.
Example: For the input [[1, 2], [2, 3], [3, 4]], the output should be 3.
Constraints:
• The result will always be a non-negative integer.
Goal: The goal is to maximize the number of events that can be attended by scheduling them on non-overlapping days.
Steps:
• 1. Sort the events based on their start day. If two events start on the same day, sort by the end day.
• 2. Use a priority queue (min-heap) to keep track of the end days of events that are currently active.
• 3. Iterate through the days and for each day, add any events that start on that day and remove events that have ended.
• 4. Track the maximum number of events that can be attended at any point in time.
Goal: The solution should handle large inputs efficiently, and the result should fit within a 32-bit integer.
Steps:
• 1 <= events.length <= 10^5
• 1 <= startDay[i] <= endDay[i] <= 10^5
Assumptions:
• Events do not overlap by default, but they may share common days.
• Input: Example 1: [[1, 2], [2, 3], [3, 4]]
• Explanation: In this case, you can attend all three events by selecting one event per day.
• Input: Example 2: [[1, 2], [2, 3], [3, 4], [1, 2]]
• Explanation: In this case, you can attend all four events by choosing the best days.
Approach: The approach involves sorting the events and using a priority queue to keep track of the events and manage overlaps efficiently.
Observations:
• Sorting the events by start day helps in managing overlaps.
• Using a priority queue allows us to quickly remove events that have ended.
• We should aim to minimize the number of overlapping events while maximizing the number of events we can attend.
Steps:
• 1. Sort the events by start day, and by end day if start days are equal.
• 2. Iterate through each day and process the events using a priority queue to manage ongoing events.
• 3. Count the number of events that can be attended by tracking the minimum end time.
Empty Inputs:
• No events: The result should be 0.
Large Inputs:
• Handling up to 10^5 events efficiently without performance degradation.
Special Values:
• Events that start and end on the same day: Handle these events appropriately.
Constraints:
• The solution should run in O(n log n) time due to sorting.
static bool cmp(vector<int> &a, vector<int> &b) {
if(a[0] == b[0]) return a[1] < b[1];
else return a[0] < b[0];
}
int maxEvents(vector<vector<int>>& e) {
int n = e.size();
sort(e.begin(), e.end(), cmp);
priority_queue<int, vector<int>, greater<int>> pq;
int i = 0, cnt = 0;
for(int d = 1; d <= 100000; d++) {
while(!pq.empty() && pq.top() < d) {
pq.pop();
}
while(i < n && e[i][0] == d) {
pq.push(e[i++][1]);
}
if(!pq.empty()) {
pq.pop();
cnt++;
}
}
return cnt;
}
1 : Comparator Function
static bool cmp(vector<int> &a, vector<int> &b) {
We define a comparator function to sort the events. If two events have the same start day, they are sorted by their end day in ascending order.
2 : Comparator Logic
if(a[0] == b[0]) return a[1] < b[1];
If two events start on the same day, we return true if the first event ends earlier than the second.
3 : Comparator Logic
else return a[0] < b[0];
If the start days are different, we return true if the first event starts earlier than the second.
4 : Function Declaration
int maxEvents(vector<vector<int>>& e) {
The 'maxEvents' function is declared, which takes a vector of events, each represented as a pair of start and end days.
5 : Event Count Initialization
int n = e.size();
We initialize 'n' to the number of events, which is the size of the vector 'e'.
6 : Sort Events
sort(e.begin(), e.end(), cmp);
We sort the events by their start day (and end day if the start days are equal) using the 'cmp' comparator.
7 : Priority Queue Declaration
priority_queue<int, vector<int>, greater<int>> pq;
We declare a priority queue to store the end days of events, sorted in ascending order.
8 : Counter Initialization
int i = 0, cnt = 0;
We initialize two variables: 'i' to track the index of events and 'cnt' to count the number of events that can be attended.
9 : Day Loop
for(int d = 1; d <= 100000; d++) {
We loop over each day from 1 to 100000, representing the possible days on which an event can take place.
10 : Pop Expired Events
while(!pq.empty() && pq.top() < d) {
We remove events from the priority queue that have already ended before the current day 'd'.
11 : Pop Expired Event
pq.pop();
We remove the event with the earliest end day from the priority queue.
12 : Add New Events
while(i < n && e[i][0] == d) {
We add all events starting on the current day 'd' to the priority queue.
13 : Push Event to Queue
pq.push(e[i++][1]);
We push the end day of the current event into the priority queue and move to the next event.
14 : Attend Event
if(!pq.empty()) {
If there are events available to attend, we proceed to attend one.
15 : Pop Attended Event
pq.pop();
We pop the event with the earliest end day from the priority queue, as it is the event we will attend.
16 : Increment Event Count
cnt++;
We increment the event count as we have successfully attended an event.
17 : Return Result
return cnt;
We return the total count of events that can be attended.
Best Case: O(n log n) for sorting the events.
Average Case: O(n log n) due to sorting and priority queue operations.
Worst Case: O(n log n), where n is the number of events.
Description: The time complexity is dominated by sorting the events.
Best Case: O(1) if there are no events.
Worst Case: O(n) for the priority queue and input storage.
Description: The space complexity is O(n) due to the storage of events and the priority queue.
| LeetCode Solutions Library / DSA Sheets / Course Catalog |
|---|
comments powered by Disqus