easyStackPattern: Stack
Maximum Concurrent Events Solution
Problem Statement
Given an array of event logs, where each log is represented by a pair of integers `[timestamp, type]`. `type = 1` indicates an event started, and `type = -1` indicates an event ended. Determine the maximum number of events that were concurrently active at any point in time. The events are inclusive of their start and end times.
Examples
Example 1:
Input:[[1, 1], [2, 1], [3, -1], [4, 1], [5, -1], [6, -1]]
Output:2
Explanation: Assuming events represent vehicle presence from the given timestamp until its corresponding exit event, we can track concurrency. At timestamp 1, one vehicle enters (concurrency 1). At timestamp 2, another vehicle enters (concurrency 2). At timestamp 3, one vehicle exits (concurrency 1). At timestamp 4, another vehicle enters (concurrency 2). At timestamp 5, one vehicle exits (concurrency 1). At timestamp 6, the last vehicle exits (concurrency 0). The maximum concurrency observed was 2.
Example 2:
Input:[[1, 1], [1, 1], [2, -1], [2, -1]]
Output:2
Explanation: At timestamp 1, two vehicles enter (concurrency 2). At timestamp 2, two vehicles exit (concurrency 0). The maximum concurrency was 2.
Example 3:
Input:[[1, 1], [2, -1]]
Output:1
Explanation: At timestamp 1, one vehicle enters (concurrency 1). At timestamp 2, it exits (concurrency 0). The maximum concurrency was 1.
Constraints
- 1 <= logs.length <= 10^5
- 1 <= logs[i][0] <= 10^9
- logs[i][1] is either 1 or -1
- Events are processed chronologically by timestamp. If timestamps are equal, start events (type 1) are processed before end events (type -1).
Time: O(N log N) due to sorting, where N is the number of logs. Space: O(N) or O(log N) depending on the sorting algorithm's space complexity.
Sort the events by timestamp. If timestamps are equal, process start events before end events. Iterate through the sorted events, maintaining a running count of active events. Increment the count for start events and decrement for end events. Keep track of the maximum count encountered during this sweep.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def maximum_concurrent_events(logs):
if not logs:
return 0
logs.sort(key=lambda x: (x[0], -x[1])) # Sort by timestamp, then type (start before end)
max_concurrency = 0
current_concurrency = 0
for timestamp, type in logs:
current_concurrency += type
max_concurrency = max(max_concurrency, current_concurrency)
return max_concurrency