Course4all
Join us on telegram
Home/dsa/Greedy/Maximum Number of Events That Can Be Attended

Maximum Number of Events That Can Be Attended

Master this topic with zero to advance depth.

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
    }
}
← Previous QuestionMinimum Initial Energy to Finish Tasks
Next Question →Combination Sum