Description:
Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.
You can attend an event i at any day d where startTimei <= d <= endTimei. Notice that you can only attend one event at any time d.
Return the maximum number of events you can attend.
Solution:
Time Complexity : O(n^2)
Space Complexity: O(n)
var maxEvents = function(events) {
let visited = {};
// Sort events: endTime smaller to bigger, if endTimes are same, prioritize startTime smaller one
events = events.sort((a,b)=>{
if(a[1]!=b[1]) return a[1] - b[1];
return a[0] - b[0];
});
let res=0;
// Loop through the events and increment the number of days we can attend a unique event
for(let k=0;k<events.length;k++) {
let event = events[k];
let start = event[0];
let end = event[1];
for(let i=start;i<=end;i++) {
// Only count a day as visited if it has an event we have not visited yet
if(!visited[i]) {
visited[i] = true;
res++;
break;
}
}
}
return res;
};
Top comments (0)