Course4all
Join us on telegram
Home/dsa/Heap / Priority Queue/Maximum Number of Events

Maximum Number of Events

Master this topic with zero to advance depth.

Maximum Number of Events

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 per day.

Return the maximum number of events you can attend.

Visual Representation

events = [[1,2],[2,3],[3,4]] Day 1: [1,2] available. Attend it. Day 2: [2,3] available. Attend it. Day 3: [3,4] available. Attend it. Total = 3 Key insight: Each day, attend the event that ends SOONEST (greedy). This leaves later-ending events available for future days.
Medium

Examples

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

Level I: Greedy - Sort by Start, Attend First Available

Intuition

Sort events by start day. On each day from 1 to maxDay, try to attend the first available event (one that hasn't been attended and whose start day <= current day). This is a greedy approach that ensures we don't miss starting opportunities.

⏱ O(maxDay * N) where maxDay is the maximum end day and N is the number of events💾 O(N) for the used set

Detailed Dry Run

events = [[1,2],[2,3],[3,4]] sorted by start Day 1: Available (not attended, start<=1, end>=1): [1,2]. Attend [1,2]. Count=1. Day 2: Available: [2,3]. Attend [2,3]. Count=2. Day 3: Available: [3,4]. Attend [3,4]. Count=3. Return 3.

java
import java.util.*;

public class Main {
    public static int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int maxDay = 0;
        for (int[] e : events) maxDay = Math.max(maxDay, e[1]);
        
        boolean[] attended = new boolean[events.length];
        int count = 0;
        
        for (int day = 1; day <= maxDay; day++) {
            // Find the event with smallest end day that starts on or before today
            int bestIdx = -1;
            for (int i = 0; i < events.length; i++) {
                if (!attended[i] && events[i][0] <= day && events[i][1] >= day) {
                    if (bestIdx == -1 || events[i][1] < events[bestIdx][1]) {
                        bestIdx = i;
                    }
                }
            }
            if (bestIdx != -1) {
                attended[bestIdx] = true;
                count++;
            }
        }
        return count;
    }

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

Level II: Sort by Start + Daily Min-End Search

Intuition

To improve on the basic search, we sort events by their start day. Each day, we identify all events that have already started and haven't been attended. Among these available events, we pick the one that ends the soonest (earliest end day). This ensures we use up events that would expire early, leaving more flexibility for the future.

⏱ O(maxDay * N) where maxDay is the duration of events and N is number of events💾 O(N) for the used tracker

Detailed Dry Run

events = [[1,4],[1,1],[2,2]] sorted. Day 1: Available: [1,4], [1,1]. Ends are 4, 1. Min end is 1. Attend [1,1]. Count=1. Day 2: Available: [1,4], [2,2]. Ends are 4, 2. Min end is 2. Attend [2,2]. Count=2. Day 3: Available: [1,4]. Attend [1,4]. Count=3. Max = 3.

java
import java.util.*;

public class Solution {
    public int maxEvents(int[][] events) {
        Arrays.sort(events, (a, b) -> a[0] - b[0]);
        int maxDay = 0;
        for (int[] e : events) maxDay = Math.max(maxDay, e[1]);
        
        boolean[] used = new boolean[events.length];
        int count = 0;
        for (int day = 1; day <= maxDay; day++) {
            int bestIdx = -1, minEnd = Integer.MAX_VALUE;
            for (int i = 0; i < events.length; i++) {
                if (events[i][0] > day) break; // Optimization from sorting
                if (!used[i] && events[i][1] >= day) {
                    if (events[i][1] < minEnd) {
                        minEnd = events[i][1];
                        bestIdx = i;
                    }
                }
            }
            if (bestIdx != -1) {
                used[bestIdx] = true;
                count++;
            }
        }
        return count;
    }
}
Approach 3

Level III: Sort by Start + Min-Heap of End Days (Optimal)

Intuition

Greedy insight: on each day, among all available events (those that have already started), we should attend the one that ends the soonest. If we sort events by start day and use a Min-Heap of end days, we can efficiently:

  1. Iterate over each day from 1 to maxDay.
  2. Add all events that start on this day to the Min-Heap.
  3. Remove all expired events (heap top end < today).
  4. If the heap isn't empty, attend the event ending soonest (pop from heap), increment count.
⏱ O(N log N) for sorting and heap operations. Each event is pushed and popped at most once.💾 O(N) for the Min-Heap

Detailed Dry Run

events = [[1,2],[2,3],[3,4]] sorted by start ptr=0

Day 1: Add events starting on 1: push end=2. Heap=[2]. Pop 2 (attend). Count=1. Day 2: Add events starting on 2: push end=3. Heap=[3]. Pop 3 (attend). Count=2. Day 3: Add events starting on 3: push end=4. Heap=[4]. Pop 4 (attend). Count=3. Return 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> minHeap = new PriorityQueue<>(); // stores end days
        int ptr = 0, n = events.length;
        int maxDay = events[n - 1][1];
        // Not exactly - maxDay needs re-scan
        int maxEndDay = 0;
        for (int[] e : events) maxEndDay = Math.max(maxEndDay, e[1]);
        
        int count = 0;
        for (int day = 1; day <= maxEndDay; day++) {
            // Add all events starting today
            while (ptr < n && events[ptr][0] == day) {
                minHeap.offer(events[ptr][1]);
                ptr++;
            }
            // Remove expired
            while (!minHeap.isEmpty() && minHeap.peek() < day) {
                minHeap.poll();
            }
            // Attend soonest-ending event
            if (!minHeap.isEmpty()) {
                minHeap.poll();
                count++;
            }
        }
        return count;
    }

    public static void main(String[] args) {
        System.out.println(maxEvents(new int[][]{{1,2},{2,3},{3,4}})); // 3
    }
}
← Previous QuestionMinimum Interval to Include Each Query
Next Question →Data Stream as Disjoint Intervals