Maximum Number of Events That Can Be Attended

This problem looks like a calendar puzzle. You have events with start and end days. You can attend only one event per day. You want to attend as many events as you can. The smart move is to handle each day in order and always attend the event that ends soonest. A min-heap keeps that soonest-ending event in reach. That pairing of greedy plus heap is what the interviewer is checking.

🎯 The Problem

You get a list of events. Each one has a start day and an end day. Here are the rules.

• Each event has a start day and an end day.
• You may attend an event on any single day in its range, start to end.
• You may attend only one event on any given day.
• You want the largest number of events you can attend.

Look at [[1,2],[2,3],[3,4]]. On day 1 attend the first event. On day 2 attend the second event. On day 3 attend the third event. So you attend all three.

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

Explanation:
  Day 1 -> attend event [1,2]
  Day 2 -> attend event [2,3]
  Day 3 -> attend event [3,4]

The danger is events that overlap. Overlap means their day ranges cross. When two events are both open on the same day, you can pick only one. So you must choose wisely.

The picture below shows the three events on a day line.

🐢 Approach 1: Try Every Choice (Brute Force)

The idea in one line: search every way of picking events.

The idea:

• For each day, try attending each open event.
• Then explore what happens after that pick.
• Back up when a path runs out. Try another.

How it works:

• This is a full search over all combinations.
• It does find the right answer.

Why it is weak:

• The number of paths grows extremely fast.
• This is exponential time.
• It crashes on more than a handful of events.

Here is the backtracking code:

def max_events(events):
    events.sort()

    def dfs(index, used_days):
        if index == len(events):
            return 0
        best = dfs(index + 1, used_days)
        start, end = events[index]
        for day in range(start, end + 1):
            if day not in used_days:
                used_days.add(day)
                best = max(best, 1 + dfs(index + 1, used_days))
                used_days.remove(day)
        return best

    return dfs(0, set())

🐌 Approach 2: Greedy On a Day Array (Better)

The idea in one line: book each event into the earliest free day in its range.

The idea:

• Sort events by end day, soonest end first.
• For each event, walk its days from start to end.
• Take the first day that is still free. Mark it used.

How it works:

• The soonest-ending event is the most urgent. Place it first.
• A boolean array remembers which days are taken.

Why it is better:

• It beats brute force by a wide margin.
• But scanning every day of every event is wasteful.
• On a wide day range this becomes slow.

Here is the day-array greedy code:

def max_events(events):
    events.sort(key=lambda item: item[1])
    last_day = max(end for start, end in events)
    used = [False] * (last_day + 1)
    answer = 0

    for start, end in events:
        for day in range(start, end + 1):
            if not used[day]:
                used[day] = True
                answer += 1
                break

    return answer

⚡ Approach 3: Greedy Day by Day With a Min-Heap (Best)

The idea in one line: walk day by day, and each day attend the open event that ends soonest.

The idea:

• Move through days from earliest to latest.
• Each day, look at events that have started and are not finished.
• Attend the one that ends soonest. This is earliest deadline first.

Why ends soonest:

• That event has the least time left.
• Skip it now and you may never get another chance.
• An event ending later still has spare days. So save the urgent one.

How it works:

• A min-heap always hands you the smallest item first. Here smallest means earliest end day.
• Sort the events by start day first.
• Each day, push every event that starts on or before that day.
• Drop any heap-top event whose end day already passed.
• If the heap is not empty, pop the top and attend it. Count it.

Why it is fast:

• Each event is pushed and popped once.
• The heap steps cost O(log n) each. So the whole run is O(n log n).

The diagram below shows the day-by-day loop.

Steps to Solve

1. Sort the events by their start day.
2. Keep a min-heap of end days for events that have started and are still open.
3. Walk through days in order. On the current day, push the end day of every event whose start day has arrived.
4. Remove from the top of the heap any event whose end day is before the current day. It is too late for that one.
5. If the heap is not empty, pop the smallest end day. Attend that event. Add one to the count.
6. Move to the next day. Stop when no events are left and the heap is empty. Return the count.

#include <stdio.h>
#include <stdlib.h>

// min-heap of end days
int heap[100000];
int heapSize = 0;

void push(int x) {
    heap[heapSize] = x;
    int i = heapSize++;
    while (i > 0 && heap[(i - 1) / 2] > heap[i]) {  // bubble up
        int tmp = heap[i]; heap[i] = heap[(i - 1) / 2]; heap[(i - 1) / 2] = tmp;
        i = (i - 1) / 2;
    }
}

int top(void) { return heap[0]; }

void pop(void) {
    heap[0] = heap[--heapSize];
    int i = 0;
    while (1) {                                      // bubble down
        int l = 2 * i + 1, r = 2 * i + 2, small = i;
        if (l < heapSize && heap[l] < heap[small]) small = l;
        if (r < heapSize && heap[r] < heap[small]) small = r;
        if (small == i) break;
        int tmp = heap[i]; heap[i] = heap[small]; heap[small] = tmp;
        i = small;
    }
}

int cmpStart(const void *a, const void *b) {
    int *ea = *(int **)a, *eb = *(int **)b;
    return ea[0] - eb[0];  // sort by start day
}

int maxEvents(int events[][2], int n) {
    int **ev = malloc(n * sizeof(int *));
    for (int i = 0; i < n; i++) ev[i] = events[i];
    qsort(ev, n, sizeof(int *), cmpStart);

    int count = 0, i = 0, day = 0;
    while (i < n || heapSize > 0) {
        if (heapSize == 0) day = ev[i][0];   // jump to next event start
        // push every event that starts on or before this day
        while (i < n && ev[i][0] <= day) { push(ev[i][1]); i++; }
        // drop events that already ended before today
        while (heapSize > 0 && top() < day) pop();
        if (heapSize > 0) { pop(); count++; } // attend soonest-ending
        day++;
    }
    free(ev);
    return count;
}

int main(void) {
    int events[3][2] = {{1, 2}, {2, 3}, {3, 4}};
    printf("%d\n", maxEvents(events, 3));  // 3
    return 0;
}

3

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int maxEvents(vector<vector<int>> &events) {
    sort(events.begin(), events.end());  // by start day
    // min-heap of end days
    priority_queue<int, vector<int>, greater<int>> heap;

    int count = 0, i = 0, n = events.size(), day = 0;
    while (i < n || !heap.empty()) {
        if (heap.empty()) day = events[i][0];   // jump to next start
        while (i < n && events[i][0] <= day) {   // push started events
            heap.push(events[i][1]);
            i++;
        }
        while (!heap.empty() && heap.top() < day) heap.pop(); // drop expired
        if (!heap.empty()) { heap.pop(); count++; }           // attend soonest end
        day++;
    }
    return count;
}

int main() {
    vector<vector<int>> events = {{1, 2}, {2, 3}, {3, 4}};
    cout << maxEvents(events) << endl;  // 3
    return 0;
}

3

import java.util.*;

public class MaxEvents {
    public static int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);  // by start day
        PriorityQueue<Integer> heap = new PriorityQueue<>(); // min-heap of end days

        int count = 0, i = 0, n = events.length, day = 0;
        while (i < n || !heap.isEmpty()) {
            if (heap.isEmpty()) day = events[i][0];  // jump to next start
            while (i < n && events[i][0] <= day) {   // push started events
                heap.offer(events[i][1]);
                i++;
            }
            while (!heap.isEmpty() && heap.peek() < day) heap.poll(); // drop expired
            if (!heap.isEmpty()) { heap.poll(); count++; }            // attend soonest end
            day++;
        }
        return count;
    }

    public static void main(String[] args) {
        int[][] events = {{1, 2}, {2, 3}, {3, 4}};
        System.out.println(maxEvents(events));  // 3
    }
}

3

import heapq


def max_events(events):
    events.sort()              # sort by start day
    heap = []                  # min-heap of end days
    count = 0
    i = 0
    n = len(events)
    day = 0

    while i < n or heap:
        if not heap:
            day = events[i][0]            # jump to next event start
        while i < n and events[i][0] <= day:
            heapq.heappush(heap, events[i][1])  # event has started
            i += 1
        while heap and heap[0] < day:
            heapq.heappop(heap)           # this event already ended
        if heap:
            heapq.heappop(heap)           # attend the soonest-ending event
            count += 1
        day += 1

    return count


events = [[1, 2], [2, 3], [3, 4]]
print(max_events(events))  # 3

3

function maxEvents(events) {
  events.sort((a, b) => a[0] - b[0]); // by start day
  const heap = []; // min-heap of end days

  const push = (x) => {
    heap.push(x);
    let i = heap.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (heap[p] <= heap[i]) break;
      [heap[p], heap[i]] = [heap[i], heap[p]];
      i = p;
    }
  };
  const pop = () => {
    const topVal = heap[0];
    const last = heap.pop();
    if (heap.length) {
      heap[0] = last;
      let i = 0;
      while (true) {
        let l = 2 * i + 1, r = 2 * i + 2, small = i;
        if (l < heap.length && heap[l] < heap[small]) small = l;
        if (r < heap.length && heap[r] < heap[small]) small = r;
        if (small === i) break;
        [heap[small], heap[i]] = [heap[i], heap[small]];
        i = small;
      }
    }
    return topVal;
  };

  let count = 0, i = 0, day = 0;
  const n = events.length;
  while (i < n || heap.length) {
    if (!heap.length) day = events[i][0];          // jump to next start
    while (i < n && events[i][0] <= day) push(events[i++][1]); // started events
    while (heap.length && heap[0] < day) pop();    // drop expired
    if (heap.length) { pop(); count++; }           // attend soonest end
    day++;
  }
  return count;
}

console.log(maxEvents([[1, 2], [2, 3], [3, 4]])); // 3

3

Let us walk through the Python version line by line, because the day-by-day greedy is easy to get slightly wrong.

The line events.sort() sorts events by start day. Sorting by start lets us add events to the heap in order, as their start day arrives.

The line heap = [] is the min-heap of end days. We store only the end day, since that is what tells us how urgent an event is.

The main loop runs while i < n or heap:. So it keeps going while there are events we have not added yet, or open events still in the heap.

The line if not heap: day = events[i][0] jumps the day forward when nothing is open. There is no point sitting on empty days. We skip straight to the next event’s start.

The first inner loop, while i < n and events[i][0] <= day:, pushes every event whose start day has arrived. After the push it is “open” and waiting in the heap.

The second inner loop, while heap and heap[0] < day:, throws away events whose end day already passed. heap[0] is the smallest end day. If even that one ended before today, it is too late, so we drop it.

The line if heap: then attends the best event. heappop removes the soonest-ending event, which is the most urgent. We add one to count. Then day += 1 moves to the next day.

⏱️ Time and Space Complexity

The brute force explores all choices, so it is exponential and not usable. The greedy version sorts once, which is O(n log n). Then each event is pushed and popped from the heap at most once, and each heap step is O(log n). So the total is O(n log n). The space is O(n) for the heap in the worst case, when many events are open at the same time.

🧩 Key Takeaways

• ✅ Sort events by start day so you can add them as their day arrives.
• ✅ Walk day by day. Keep open events in a min-heap of end days.
• ✅ Each day, attend the event that ends soonest. That is earliest deadline first.
• ✅ Drop events whose end day already passed before you pick one.
• ✅ The whole thing is O(n log n), driven by the sort and the heap steps.

🚀 What’s Next?

• Reorganize String
• Maximum Profit in Job Scheduling