Maximum Number of Events That Can Be Attended

Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayiand 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.

Events Calender

Example 1:

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.

Example 2:

Input: events= [[1,2],[2,3],[3,4],[1,2]]
Output: 4

Example 3:

Input: events = [[1,4],[4,4],[2,2],[3,4],[1,1]]
Output: 4

Example 4:

Input: events = [[1,100000]]
Output: 1

Example 5:

Input: events = [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[1,7]]
Output: 7

Constraints:

  • 1 <= events.length <= 105
  • events[i].length == 2
  • 1 <= startDayi <= endDayi <= 105

Solution

  • Sort events increased by start time.
  • Priority queue pq keeps the current open events.
  • Iterate from the day 1 to day 100000,
  • Each day, we add new events starting on day d to the queue pq.
  • Also we remove the events that are already closed.
  • Then we greedily attend the event that ends soonest.
  • If we can attend a meeting, we increment the result count.

class Solution {
    public int maxEvents(int[][] events) {
        
        if(events == null || events.length == 0){
            return 0;
        }
        Arrays.sort(events, (a,b) -> Integer.compare(a[0], b[0]));
        Queue<Integer> minHeap = new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer i1, Integer i2){
                return Integer.compare(i1, i2);
            }
        });
        int count = 0;
        int j = 0;
        for(int d = 1 ; d <= 100000 ; d++){
            
            while(!minHeap.isEmpty() && minHeap.peek() < d){
                minHeap.poll();
            }
            while( j < events.length){
                int[] curEvent = events[j];
                if(curEvent[0] > d){
                    break;
                }
                if(curEvent[0] == d){
                    minHeap.offer(curEvent[1]);
                }
                j++;
            }
            if(!minHeap.isEmpty()){
                minHeap.poll();
                count++;
            }
        }
        return count;
    }
}

Complexity

  • Time Complexcity: O(d + nlogn), where D is the range of A[i][1]
  • Space Complexcity: O(N)

Categories: Heap

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s