Design Event Manager - Video Solutions
Leetcode 3885 | Design Event Manager | Leetcode weekly contest 495
Design Event Manager - Video Solution
Watch 7 video solutions for Design Event Manager, a medium level problem involving Array, Hash Table, Design. This walkthrough by CodeWithMeGuys has 331 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
You are given an initial list of events, where each event has a unique eventId and a priority.
Implement the EventManager class:
EventManager(int[][] events)Initializes the manager with the given events, whereevents[i] = [eventIdi, priorityi].void updatePriority(int eventId, int newPriority)Updates the priority of the active event with ideventIdtonewPriority.int pollHighest()Removes and returns theeventIdof the active event with the highest priority. If multiple active events have the same priority, return the smallesteventIdamong them. If there are no active events, return -1.
An event is called active if it has not been removed by pollHighest().
Example 1:
Input:
["EventManager", "pollHighest", "updatePriority", "pollHighest", "pollHighest"]
[[[[5, 7], [2, 7], [9, 4]]], [], [9, 7], [], []]
Output:
[null, 2, null, 5, 9]
Explanation
EventManager eventManager = new EventManager([[5,7], [2,7], [9,4]]); // Initializes the manager with three eventseventManager.pollHighest(); // both events 5 and 2 have priority 7, so return the smaller id 2
eventManager.updatePriority(9, 7); // event 9 now has priority 7
eventManager.pollHighest(); // remaining highest priority events are 5 and 9, return 5
eventManager.pollHighest(); // return 9
Example 2:
Input:
["EventManager", "pollHighest", "pollHighest", "pollHighest"]
[[[[4, 1], [7, 2]]], [], [], []]
Output:
[null, 7, 4, -1]
Explanation
EventManager eventManager = new EventManager([[4,1], [7,2]]); // Initializes the manager with two eventseventManager.pollHighest(); // return 7
eventManager.pollHighest(); // return 4
eventManager.pollHighest(); // no events remain, return -1
Constraints:
1 <= events.length <= 105events[i] = [eventId, priority]1 <= eventId <= 1091 <= priority <= 109- All the values of
eventIdineventsare unique. 1 <= newPriority <= 109- For every call to
updatePriority,eventIdrefers to an active event. - At most
105calls in total will be made toupdatePriorityandpollHighest.
Approach Overview
Problem Overview: Design a system that manages events and supports operations such as scheduling, removing, and retrieving events efficiently. The core challenge is keeping events ordered so queries like the next upcoming event can be answered quickly.
Approach 1: Unordered List Simulation (O(n) time per query, O(n) space)
The most direct implementation stores all events in a simple list or array. Each insertion appends to the list in O(1) time. When you need to find the next valid event or process events in order, you iterate through the entire list to locate the smallest valid timestamp or identifier. This makes queries O(n), which becomes expensive as the number of events grows. This approach is useful for understanding the requirements but does not scale well for large input sizes.
Approach 2: Sorted Set (Balanced BST) (O(log n) operations, O(n) space)
A more efficient design stores events inside a sorted set, typically implemented using a balanced binary search tree such as TreeSet in Java or ordered structures in C++ and Python. The key idea is to maintain events automatically sorted by their time or priority. When a new event is scheduled, you insert it into the sorted structure in O(log n). When an event is removed or completed, deletion also takes O(log n).
This ordering enables fast queries. If you need the earliest event, you simply read the first element of the sorted structure. If the problem requires locating the next event after a given timestamp, you perform a ceiling or lower_bound style lookup, which also runs in O(log n). The structure handles ordering automatically, eliminating the need for repeated scans.
The sorted set design works well because event managers naturally require ordered scheduling. By delegating ordering to a balanced tree, the implementation remains clean while guaranteeing predictable performance. This approach is closely related to techniques used in binary search over ordered data and tree-based structures discussed in data structures. Many implementations rely directly on a sorted set abstraction.
Recommended for interviews: The sorted set approach is the expected solution. Interviewers want to see that you recognize the need for ordered retrieval and choose a structure that supports insertion, deletion, and neighbor queries in O(log n). Starting with the brute force list demonstrates understanding of the problem, but switching to a balanced tree or sorted set shows strong algorithmic judgment.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Unordered List Simulation | O(n) per query | O(n) | Small datasets or when event ordering is rarely queried |
| Sorted Set (Balanced BST) | O(log n) insert, delete, query | O(n) | General case where events must remain ordered and queries occur frequently |