# Maximum Number of Events That Can Be Attended

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.

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