Code Implementation

import heapq

class Solution:
    def maxEvents(self, events):
        events.sort()
        min_heap = []
        res = 0
        i = 0
        n = len(events)
        day = 1
        last_day = max(e[1] for e in events)

        for day in range(1, last_day + 1):
            # Add all events that start today
            while i < n and events[i][0] == day:
                heapq.heappush(min_heap, events[i][1])
                i += 1
            # Remove events that have already ended
            while min_heap and min_heap[0] < day:
                heapq.heappop(min_heap)
            # Attend the event that ends earliest
            if min_heap:
                heapq.heappop(min_heap)
                res += 1
        return res
      

#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        sort(events.begin(), events.end());
        priority_queue<int, vector<int>, greater<int>> minHeap;
        int i = 0, res = 0, n = events.size();
        int lastDay = 0;
        for (auto& e : events) lastDay = max(lastDay, e[1]);
        for (int day = 1; day <= lastDay; ++day) {
            while (i < n && events[i][0] == day)
                minHeap.push(events[i++][1]);
            while (!minHeap.empty() && minHeap.top() < day)
                minHeap.pop();
            if (!minHeap.empty()) {
                minHeap.pop();
                ++res;
            }
        }
        return res;
    }
};
      

import java.util.*;

class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        int i = 0, res = 0, n = events.length;
        int lastDay = 0;
        for (int[] e : events) lastDay = Math.max(lastDay, e[1]);
        for (int day = 1; day <= lastDay; ++day) {
            while (i < n && events[i][0] == day)
                minHeap.offer(events[i++][1]);
            while (!minHeap.isEmpty() && minHeap.peek() < day)
                minHeap.poll();
            if (!minHeap.isEmpty()) {
                minHeap.poll();
                ++res;
            }
        }
        return res;
    }
}
      

class MinHeap {
    constructor() {
        this.heap = [];
    }
    push(val) {
        this.heap.push(val);
        let i = this.heap.length - 1;
        while (i > 0) {
            let p = (i - 1) >> 1;
            if (this.heap[p] <= this.heap[i]) break;
            [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
            i = p;
        }
    }
    pop() {
        if (this.heap.length === 0) return null;
        let out = this.heap[0];
        let end = this.heap.pop();
        if (this.heap.length > 0) {
            this.heap[0] = end;
            let i = 0, l = this.heap.length;
            while (true) {
                let left = 2 * i + 1, right = 2 * i + 2, smallest = i;
                if (left < l && this.heap[left] < this.heap[smallest]) smallest = left;
                if (right < l && this.heap[right] < this.heap[smallest]) smallest = right;
                if (smallest === i) break;
                [this.heap[i], this.heap[smallest]] = [this.heap[smallest], this.heap[i]];
                i = smallest;
            }
        }
        return out;
    }
    peek() {
        return this.heap.length ? this.heap[0] : null;
    }
    size() {
        return this.heap.length;
    }
}

var maxEvents = function(events) {
    events.sort((a, b) => a[0] - b[0]);
    let minHeap = new MinHeap();
    let i = 0, res = 0, n = events.length;
    let lastDay = Math.max(...events.map(e => e[1]));
    for (let day = 1; day <= lastDay; ++day) {
        while (i < n && events[i][0] === day)
            minHeap.push(events[i++][1]);
        while (minHeap.size() && minHeap.peek() < day)
            minHeap.pop();
        if (minHeap.size()) {
            minHeap.pop();
            ++res;
        }
    }
    return res;
};
      

Problem Description

You are given a list of events, where each event is represented as an array [startDay, endDay]. Each event can be attended on any day between its startDay and endDay (inclusive). However, you can only attend one event per day.

The goal is to find the maximum number of events you can attend, given that you cannot attend more than one event on the same day, and you cannot attend the same event more than once.

• Each event can only be attended once, and only on a single day within its interval.
• You may choose which day to attend each event, as long as the day is within the event's interval and does not conflict with other chosen events.
• Return the maximum number of events you can attend.

Thought Process

The first idea is to try all possible combinations of which events to attend on which days, but this quickly becomes infeasible as the number of events grows, due to the exponential number of possibilities.

Instead, we can think about this problem as a type of scheduling problem. Since each event has a range of days it can be attended, and we can only attend one event per day, our goal is to "pack" as many events as possible into the available days without overlapping.

We notice that if we always try to attend the event that ends earliest, we leave more room for future events. This is similar to the classic greedy strategy for interval scheduling: always pick the job/event that finishes soonest.

To efficiently manage which events are available to attend on each day, we can use a min-heap (priority queue) to always pick the event with the earliest end day.

Solution Approach

• Step 1: Sort the events.
  First, sort the list of events by their start day. This allows us to process events in the order they become available.
• Step 2: Use a min-heap for end days.
  We use a min-heap (priority queue) to keep track of all events that are currently available to attend (i.e., their start day is less than or equal to the current day). The heap is ordered by the event's end day, so we always attend the event that will end soonest.
• Step 3: Iterate by day.
  We iterate from the earliest day to the latest possible end day among all events. For each day:
  • Add to the heap all events that start on that day.
  • Remove from the heap any events whose end day is before the current day (since they can no longer be attended).
  • If the heap is not empty, attend the event with the earliest end day (remove it from the heap and increment the count).
• Step 4: Continue until all days are processed.
  When all days have been processed, the count represents the maximum number of events that can be attended.

The use of a heap ensures that we can efficiently select the best event to attend each day, and sorting the events ensures we process them in the correct order.

Example Walkthrough

Let's walk through an example with the following events:
events = [[1,2], [2,3], [3,4]]

1. Sort the events: Already sorted by start day.
2. Find the last day: The last end day is 4.
3. Day 1:
   • Add events starting today: [1,2] (end day 2) goes into the heap.
   • Heap: [2]
   • Attend event with earliest end day: Attend [1,2].
4. Day 2:
   • Add events starting today: [2,3] (end day 3) goes into the heap.
   • Heap: [3]
   • Attend event with earliest end day: Attend [2,3].
5. Day 3:
   • Add events starting today: [3,4] (end day 4) goes into the heap.
   • Heap: [4]
   • Attend event with earliest end day: Attend [3,4].
6. Day 4:
   • No new events start today.
   • Heap is empty.
   • No event to attend.

The answer is 3: we can attend all events, each on a distinct day.

Time and Space Complexity

• Brute-force approach:
  Trying all possible assignments of events to days is exponential in the number of events, i.e., O(n!), which is not feasible for large inputs.
• Optimized approach:
  
  • Sorting the events: O(n log n), where n is the number of events.
  • Processing each day and managing the heap: Each event is pushed and popped at most once, so total heap operations are O(n log n).
  • Overall time complexity: O(n log n).
  • Space complexity: O(n) for the heap and the sorted events.

Summary

In this problem, we maximize the number of events that can be attended by always attending the event that ends soonest among those available each day. By sorting events and using a min-heap to track the soonest-ending events, we efficiently schedule attendance and avoid conflicts. This greedy approach is both optimal and efficient, making use of classic scheduling techniques and priority queues.