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, where events[i] = [eventIdi, priorityi].void updatePriority(int eventId, int newPriority) Updates the priority of the active event with id eventId to newPriority.int pollHighest() Removes and returns the eventId of the active event with the highest priority. If multiple active events have the same priority, return the smallest eventId among 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 eventsExample 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 events
Constraints:
1 <= events.length <= 105events[i] = [eventId, priority]1 <= eventId <= 1091 <= priority <= 109eventId in events are unique.1 <= newPriority <= 109updatePriority, eventId refers to an active event.105 calls in total will be made to updatePriority and pollHighest.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.
We define a sorted set sl to store tuples of priority and id (-priority, eventId) for all active events, and a hash map d to store the priority of each event.
During initialization, we iterate over the given event list, add the tuple of priority and id for each event into the sorted set sl, and store each event's priority in the hash map d.
For the updatePriority(eventId, newPriority) operation, we first retrieve the old priority of the event from the hash map d, then remove the tuple of the old priority and event id from the sorted set sl, add the tuple of the new priority and event id into sl, and update the event's priority in d.
For the pollHighest() operation, we first check whether the sorted set sl is empty. If it is, return -1. Otherwise, we retrieve the event with the highest priority (i.e., the first element) from sl, remove its tuple, delete the event's priority information from d, and return the event's id.
In terms of time complexity, initialization takes O(n log n) time, where n is the number of initial events. Each call to updatePriority and pollHighest takes O(log n) time. The space complexity is O(n), where n is the number of active events.
| 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 |
Practice Design Event Manager with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor