Course4all

Maximum Number of Events That Can Be Attended

Expert Answer & Key Takeaways

A complete guide to understanding and implementing Greedy.

Maximum Number of Events That Can Be Attended

You are given an array of events where events[i] = [startDay_i, endDay_i]. Every event i starts at startDay_i and ends at endDay_i. You can attend an event i at any day d where startDay_i <= d <= endDay_i.
You can only attend one event at any day d.
Return the maximum number of events you can attend.

Visual Representation

Events: [[1, 2], [1, 2], [3, 3]] Day 1: Attend [1, 2] (Event 1) Day 2: Attend [1, 2] (Event 2) Day 3: Attend [3, 3] (Event 3) Result: 3
Medium

Examples

Input: events = [[1,2],[1,2],[3,3]]
Output: 3
You can attend all 3 events.
Approach 1

Level I: Brute Force (Recursive Scheduling)

Intuition

Try every possible combination of events you could attend. For each subset of events, check if there exists a valid day for each event such that no two events are attended on the same day and each event is attended within its [start, end] range.

Thought Process

  1. Use recursion to try and attend or skip each event.
  2. When attending an event, try every possible day in its range [start,end][start, end] that hasn't been used yet.
  3. Keep track of the maximum number of events attended.
  4. This approach is O(2N⋅MaxDay)O(2^N \cdot MaxDay) or worse if checking all day combinations.

Pattern: Backtracking / Search

⏱ O(2^N * MaxDay) - Exponential.💾 O(N + MaxDay) for recursion and tracking used days.
java
import java.util.*;

public class Main {
    public static int maxEvents(int[][] events) {
        // Brute force would involve trying all subsets and checking validity.
        return -1; // Placeholder
    }

    public static void main(String[] args) {
        System.out.println("Brute force tries all possible subsets of events.");
    }
}
Approach 2

Level II: Greedy Simulation (O(N^2))

Intuition

For each day, we scan all available events that have not been attended yet and pick the one that ends the earliest. This is a direct simulation of the optimal strategy without a Priority Queue.

Thought Process

  1. Sort events by startDay.
  2. Maintain a used boolean array.
  3. For each day d from minStart to maxEnd:
    • Find an unvisited event i such that events[i].start <= d and events[i].end >= d and it has the minimum end time among all such candidates.
    • If found, mark used[i] = true and increment count.

Pattern: Greedy Scanning

⏱ O(MaxDay * N).💾 O(N) for used array.

Detailed Dry Run

Events: [[1,2],[1,2],[3,3]] Day 1: Both [1,2] available. Pick one. Mark used. Day 2: Only other [1,2] available. Pick it. Mark used. Day 3: [3,3] available. Pick it. Mark used. Total: 3.
java
public class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[1] - b[1]);
        int n = events.length, res = 0;
        boolean[] usedDays = new boolean[100001];
        for (int[] e : events) {
            for (int d = e[0]; d <= e[1]; d++) {
                if (!usedDays[d]) {
                    usedDays[d] = true;
                    res++;
                    break;
                }
            }
        }
        return res;
    }
}
Approach 3

Level III: Optimal Greedy (Min-Heap + Sorting)

Intuition

On any given day, if multiple events are available, we should prioritize the one that ends the earliest. This is because an event with a later end day can potentially be attended on a future day.

Thought Process

  1. Sort events by startDay.
  2. Use a Min-Heap to store the end days of currently available events.
  3. Iterate through days:
    • Add all events starting today to the heap.
    • Remove events from the heap that have already ended.
    • If the heap is not empty, attend the event that ends the earliest (pop from heap) and increment count.

Pattern: Greedy / Priority Queue

⏱ O(N log N + MaxDay log N) - Sorting and heap operations.💾 O(N) for the heap.

Detailed Dry Run

events = [[1,2], [1,2], [3,3]]
DayAdd to HeapExpiredAttendHeap
1[2, 2]-Attend(2)[2]
2--Attend(2)[]
3[3]-Attend(3)[]
Result: 3
java
import java.util.*;

public class Main {
    public static int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        int i = 0, n = events.length, res = 0;
        for (int d = 1; d <= 100000; d++) {
            while (i < n && events[i][0] == d) pq.add(events[i++][1]);
            while (!pq.isEmpty() && pq.peek() < d) pq.poll();
            if (!pq.isEmpty()) {
                pq.poll();
                res++;
            }
            if (pq.isEmpty() && i == n) break;
        }
        return res;
    }

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

Course4All Technical Board

Verified Expert

Senior Software Engineers & Algorithmic Experts

Our DSA content is authored and reviewed by engineers from top tech firms to ensure optimal time and space complexity analysis.

Pattern: 2026 Ready
Updated: Weekly
← Previous QuestionMinimum Initial Energy to Finish Tasks
Next Question →Combination Sum