Maximum Number of Events That Can Be Attended Solution In C++/Java/Python/Javascript
Problem Description
You are given an array of events where events[i] = [startDay i, endDay i]. Every event i starts at startDay i and ends at endDay i.
You can attend an event i at any day d where startTime i <= d <= endTime i. You can only attend one event at any time d.
Return the maximum number of events you can attend.
Example
Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.
Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4
Explanation: Attend first event at day 1,event 4 at day 2 ,event 2 at day 3 and event 3 at day 4.In this way all four events can be attained.
Constraints:
- 1 <= events.length <= 10^5
- events[i].length == 2
- 1 <= startDayi <= endDayi <= 10^5
You're given events with start and end days, and you need to maximize the number of events you can attend without overlapping days. Each event can be attended on any day within its interval. A practical initial approach is to sort the events—either by their start or end times—to simplify tracking which events are available and to plan your schedule effectively.
Optimal Approach
Intuition
Imagine you’re planning to attend a week-long festival with many events spread across different days. Each event has a start day and an end day, and you can choose to attend an event on any day within that range. However, since you can only attend one event per day, your goal is to attend as many events as possible.
Now, consider that on day d, several events have started, each with a different end time. To maximize the number of events you attend, you need to decide which event to choose on day d. Would you opt for an event that ends later or one that ends earlier? It’s clear that you should choose the event that ends the earliest because an event ending later might still be available on another day, allowing you to free up your current day for an event that cannot be postponed. Also the events with ending day less than day d are now useless for us as they cannot be attended now.
Translating this into code, one way to approach the problem is to maintain a list of events for each day, traverse the list each day, and select the event with the smallest end time. However, if the number of events is large, scanning through all events every day becomes inefficient.
Also the events with ending day less than day d are now useless for us as they cannot be attended now.
This is where a heap (or priority queue) comes into play. A heap is a specialized data structure that helps you quickly retrieve the smallest (or largest) element—in our case, the event with the earliest end time—without scanning through the entire list every time.
What is Heap?
A heap is a specialized tree-based data structure often used to implement priority queues. Heaps are usually implemented as complete binary trees (every level is fully filled except possibly the last, and all nodes are as far left as possible), which allows them to be efficiently stored in an array. With a heap, you can quickly access the minimum or maximum element in constant time, and insertion or deletion operations take logarithmic time. This makes heaps extremely useful in algorithms that require repeated retrieval of the "best" element, like scheduling tasks or sorting data with heapsort.
What is min-heap?
A min-heap is a specialized binary tree-based data structure where the smallest element is always at the root. This means that for any given node in the tree, its value is less than or equal to the values of its children. Because of this property, you can quickly access the minimum element at any time. Additionally, a min-heap is usually implemented as a complete binary tree, which means all levels of the tree are fully filled except possibly the last level, and all nodes in the last level are as far left as possible.
What is max-heap?
A max-heap is a complete binary tree data structure where every parent node has a value greater than or equal to its children, ensuring that the largest element is always at the root. This property makes it easy to quickly access the maximum element. Like a min-heap, a max-heap is typically implemented using an array, which efficiently represents the complete binary tree.
General Operations on Heap:
- Insertion:
Inserting an element takes O(log n) time because after placing the new element at the end of the array, you "bubble up" (or "sift up") to restore the heap property. - Removal (Extract-Min/Extract-Max):
Removing the root element (the minimum in a min-heap or maximum in a max-heap) also takes O(log n) time since after removal, you "bubble down" (or "sift down") the last element placed at the root to reestablish the heap property. - Peek (Find-Min/Find-Max):
Retrieving the root element is an O(1) operation because it is always at the front of the array. - Building a Heap:
Building a heap from an unsorted array can be done in O(n) time using a bottom-up heapify process. - Space Complexity:
The heap uses O(n) space to store n elements.
With a heap, you can add an event (i.e., its end time) in logarithmic time. Similarly, removing the event that ends earliest is also done in logarithmic time. This efficiency is crucial when you have many events.
The heap automatically keeps the event with the smallest end time at the top. So, when you need to choose an event on day d, you simply look at the top of the heap. If the event’s end time is at least day d (meaning it’s still available), you attend it. Otherwise, you discard it and check the next one.
Why does the greedy strategy of choosing the event with the earliest end time maximize the number of events you can attend?
Choosing the event that ends earliest is optimal because it minimizes the “occupied” time on your schedule, leaving as many days as possible free for attending subsequent events.
- Intuition: If you attend an event that ends later, you might miss the opportunity to attend a shorter event available on an earlier day.
- Real-life Analogy: Imagine you have two events available on the same day: one ends at 2 PM and the other at 5 PM. Attending the 2 PM event means you’re free for later events, whereas the 5 PM event occupies a larger portion of your day, possibly conflicting with other events.
- Conclusion: By always choosing the event that ends earliest, you maximize the remaining days available, thereby increasing the total number of events you can attend.
Approach
- Sort the Events:
Begin by sorting the array of events based on their start days. This makes it easier to know which events become available as you iterate through each day. - Determine the Maximum End Day:
Traverse the sorted events to find the maximum end day. This value defines the time frame you need to consider for attending events. - Initialize a Min-Heap:
Create a priority queue (min-heap) that will store the end days of the events. This allows you to quickly access the event that ends the earliest, ensuring you attend events that leave you more room for future ones. - Iterate Through Each Day:
Loop through each day from day 1 up to the maximum end day. For every day, perform the following steps: - Remove Expired Events:
On the current day, remove events from the heap that have already expired (i.e., events whose end day is before the current day) because they can no longer be attended. - Add New Available Events:
Add all events that start on the current day to the heap. This updates your pool of available events with the ones that you can now attend. - Attend the Best Possible Event:
If there is any event available in the heap (i.e., the heap is not empty), attend the event with the earliest end day by removing it from the heap and incrementing your count of attended events. - Early Termination Check:
If the heap is empty and all events have been processed, exit the loop early since no more events can be attended. - Return the Total Count:
Finally, return the count of events you managed to attend, which represents the maximum number of events you can participate in.
Dry Run
Step 1: Input and Sorting
• Start with the given list of events: [[1,2], [2,3], [3,4]].
• Each event consists of a start day and an end day, meaning you can attend the event on any day within this range.
• Sort the events based on their start days to process them in a structured manner.
• After sorting, the events remain [[1,2], [2,3], [3,4]], as they are already in order.
Step 2: Find Maximum End Day
• Traverse through the sorted events to determine the latest possible day you need to consider.
• The first event ends on day 2, the second event ends on day 3, and the third event ends on day 4.
• The maximum end day is found to be 4, meaning the latest day to check for possible event attendance is day 4.
Step 3: Initialize Variables
• Set a pointer i = 0 to track which events have been processed from the sorted list.
• Initialize a min-heap (pq) to store the end days of events that are currently available.
• Set ans = 0 to count the total number of events attended.
Step 4: Iterate Through Each Day
• Start iterating from day 1 up to the maximum end day (4).
• For each day, perform the necessary operations to determine if an event can be attended.
Step 5: Remove Expired Events
• Before processing new events, remove events from pq whose end day is before the current day.
• If an event’s end day is less than the current day, it means it is no longer available to attend.
• This ensures that only valid events are considered for attendance.
Step 6: Add New Available Events
• Check all events that start on the current day and add their end days to pq.
• This step ensures that all currently available events are tracked efficiently.
• The use of a min-heap ensures that events ending earlier are prioritized.
Step 7: Attend an Event
• If pq is not empty, pop the smallest end day from pq.
• This means attending the event that will expire the soonest, ensuring more flexibility for future days.
• Increment ans by 1 to indicate that an event was attended.
Step 8: Early Termination Check
• If pq is empty and all events have been processed, there are no more events left to attend.
• Exit the loop early to avoid unnecessary iterations.
Step 9: Return the Result
• The final value of ans represents the maximum number of events that could be attended.
• For the given input [[1,2], [2,3], [3,4]], the maximum number of events attended is 3.
• The output is returned as 3.
Code for All Languages
Maximum Number of Events That Can Be Attended solution in C++ :Optimal
class Solution {
public:
int maxEvents(vector<vector<int>>& arr) {
int n=arr.size();
int maxDay=0;
sort(arr.begin(),arr.end());
priority_queue<int,vector<int>,greater<int>> pq;
for(int i=0;i<n;i++){
maxDay=max(maxDay,arr[i][1]);
}
sort(arr.begin(),arr.end());
int i=0;int ans=0;
//scheduling best possible event for a particular day.
for(int d=1;i<=maxDay+1;d++){
while(pq.size() && pq.top()<d){
pq.pop();
}
while(i<n && arr[i][0]==d){
pq.push(arr[i][1]);
i++;
}
if(pq.size() && pq.top()>=d){
pq.pop();
ans++;
}
if(pq.size()==0 && i==n){
break;
}
}
return ans;
}
};
Maximum Number of Events That Can Be Attended solution in Java :Optimal
import java.util.Arrays;
import java.util.PriorityQueue;
class Solution {
public int maxEvents(int[][] events) {
int n = events.length;
int maxDay = 0;
// Sort events by their start day
Arrays.sort(events, (a, b) -> a[0] - b[0]);
// Compute the maximum ending day
for (int i = 0; i < n; i++) {
maxDay = Math.max(maxDay, events[i][1]);
}
PriorityQueue<Integer> pq = new PriorityQueue<>();
int i = 0, ans = 0;
// Iterate through each day up to maxDay
for (int d = 1; d <= maxDay; d++) {
// Remove events that have already ended
while (!pq.isEmpty() && pq.peek() < d) {
pq.poll();
}
// Add all events that start on day d
while (i < n && events[i][0] == d) {
pq.offer(events[i][1]);
i++;
}
// Attend the event that ends the earliest
if (!pq.isEmpty()) {
pq.poll();
ans++;
}
// If there are no remaining events and no upcoming events, break early.
if (pq.isEmpty() && i == n) {
break;
}
}
return ans;
}
}
Maximum Number of Events That Can Be Attended solution in Python :Optimal
import heapq
from typing import List
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
# Sort events by their start day.
events.sort(key=lambda x: x[0])
n = len(events)
# Determine the maximum end day.
max_day = max(event[1] for event in events) if events else 0
event_queue = []
i = 0
ans = 0
# Iterate through each day from 1 to max_day.
for d in range(1, max_day + 1):
# Remove events that have already ended.
while event_queue and event_queue[0] < d:
heapq.heappop(event_queue)
# Add all events that start today.
while i < n and events[i][0] == d:
heapq.heappush(event_queue, events[i][1])
i += 1
# Attend the event that ends the earliest.
if event_queue:
heapq.heappop(event_queue)
ans += 1
# If there are no ongoing events and no more events to add, exit early.
if not event_queue and i == n:
break
return ans
Maximum Number of Events That Can Be Attended solution in Javascript :Optimal
// Custom MinHeap implementation
class MinHeap {
constructor() {
this.heap = [];
}
parent(i) {
return Math.floor((i - 1) / 2);
}
left(i) {
return 2 * i + 1;
}
right(i) {
return 2 * i + 2;
}
push(val) {
this.heap.push(val);
this._heapifyUp(this.heap.length - 1);
}
pop() {
if (this.heap.length === 0) return undefined;
const root = this.heap[0];
const end = this.heap.pop();
if (this.heap.length > 0) {
this.heap[0] = end;
this._heapifyDown(0);
}
return root;
}
peek() {
return this.heap[0];
}
size() {
return this.heap.length;
}
_heapifyUp(index) {
while (index > 0) {
let parentIndex = this.parent(index);
if (this.heap[parentIndex] <= this.heap[index]) break;
[this.heap[parentIndex], this.heap[index]] = [this.heap[index], this.heap[parentIndex]];
index = parentIndex;
}
}
_heapifyDown(index) {
const length = this.heap.length;
while (true) {
let leftIndex = this.left(index);
let rightIndex = this.right(index);
let smallest = index;
if (leftIndex < length && this.heap[leftIndex] < this.heap[smallest]) {
smallest = leftIndex;
}
if (rightIndex < length && this.heap[rightIndex] < this.heap[smallest]) {
smallest = rightIndex;
}
if (smallest !== index) {
[this.heap[index], this.heap[smallest]] = [this.heap[smallest], this.heap[index]];
index = smallest;
} else {
break;
}
}
}
}
// Main solution function
function maxEvents(events) {
// Sort events by start day.
events.sort((a, b) => a[0] - b[0]);
const n = events.length;
let maxDay = 0;
// Determine the maximum end day.
for (let i = 0; i < n; i++) {
maxDay = Math.max(maxDay, events[i][1]);
}
const minHeap = new MinHeap();
let i = 0;
let ans = 0;
// Iterate through each day from 1 to maxDay.
for (let d = 1; d <= maxDay; d++) {
// Remove events that have already ended.
while (minHeap.size() > 0 && minHeap.peek() < d) {
minHeap.pop();
}
// Add all events that start on day d.
while (i < n && events[i][0] === d) {
minHeap.push(events[i][1]);
i++;
}
// Attend the event that ends the earliest.
if (minHeap.size() > 0) {
minHeap.pop();
ans++;
}
// Early exit if no events are left to process.
if (minHeap.size() === 0 && i === n) break;
}
return ans;
}
Maximum Number of Events That Can Be Attended complexity analysis:Time Complexity O(n log n).
The solution involves sorting, iterating over days, and using a min-heap (priority queue) to efficiently track available events. Let's analyze each step carefully.
Step 1: Sorting the Events: O(n log n)
• The events array is sorted based on the start day.
• Sorting an array of size n takes O(n log n) using standard sorting algorithms like QuickSort or MergeSort.
• This is the first major factor contributing to the overall complexity.
Step 2: Finding the Maximum End Day: O(n)
• We iterate over the list of events to determine the latest possible day an event can end.
• This requires a single scan of the array, which takes O(n) time.
Step 3: Iterating Over Days from 1 to maxDay: O(maxDays)
• The loop runs from day = 1 to maxDay, which is at most 100000 (10⁵) in the worst case.
• However, the number of distinct days for processing events is limited to the number of events n, because there cannot be more days processed than events themselves.
• Hence, the effective number of iterations is O(n), not O(10⁵), since we terminate early when all events are processed.
Step 4: Processing Each Event (Heap Operations): O(n log n)
For each day, we perform the following operations:
Removing Expired Events from the Heap:O(n log n).
• Every event is pushed into the heap once and removed once.
• Removing an element from a min-heap takes O(log n) in the worst case.
• Since each event is inserted and removed only once, the total removal cost across all days is O(n log n).
Adding New Events to the Heap: O(n log n).
• Each event is pushed into the min-heap exactly once.
• Inserting an element into a heap takes O(log n) time.
• Since all n events are inserted once, the total insertion cost is O(n log n).
Attending an Event (Popping from Heap):O(n log n)
• Each event attended is removed from the heap (once per event).
• Since an event is attended once, this also contributes O(n log n) in total.
Since O(n log n) dominates O(n), the final time complexity of the algorithm is O(n log n).
Maximum Number of Events That Can Be Attended complexity analysis: Space Complexity O(n ).
Auxiliary Space Complexity: 0(n)
• Sorting the events can take O(1) space if an in-place algorithm is used, or up to O(n) if not.
• The min-heap may store up to n event end days, contributing O(n) space.
• Other variables use constant O(1) space.
• Overall auxiliary space complexity is O(n).
Total Space Complexity: 0(n)
• The input events array itself uses O(n) space.
• Additional space for the heap and potential non in-place sorting adds up to O(n).
• Thus, the overall total space complexity is O(n).
Learning Tip
Now we have successfully tackled this problem, let's try these similar problems.
Similar Problems :
This problem extends the event scheduling challenge by assigning a value to each event along with its start and end times. The objective is to select at most k non-overlapping events such that the sum of their values is maximized.
This problem involves scheduling taxi rides where each ride is defined by its start time, end time, and tip. The earnings for a ride are calculated based on its duration plus the tip received. The goal is to choose a set of non-overlapping rides that maximizes the taxi driver's total earnings.