Driver Availability Monitor
Uber's operations heavily rely on real-time driver availability to ensure efficient ride-hailing services. Imagine a city divided into a series of N logical zones, indexed from 0 to N-1. At any given moment, each zone has a certain number of available drivers. As drivers go online/offline or move between zones, their availability count changes. We need a system to efficiently track these changes and provide quick insights into driver distribution across different areas.
This problem asks you to implement a data structure that can handle dynamic updates to driver counts in individual zones and perform two types of critical queries over arbitrary ranges of zones: calculating the total available drivers and identifying the maximum availability in any single zone within a given region.
Implement the DriverAvailabilityMonitor class with the following methods:
constructor(initialDrivers: number[]): Initializes the monitoring system with an array initialDrivers where initialDrivers[i] represents the initial number of available drivers in zone i.updateDrivers(zoneIndex: number, newCount: number): void: Updates the number of available drivers in the specified zoneIndex to newCount.queryTotalAvailable(startZone: number, endZone: number): number: Returns the sum of available drivers in all zones from startZone to endZone (inclusive).queryMaxAvailableZone(startZone: number, endZone: number): number: Returns the maximum number of available drivers found in any single zone within the range startZone to endZone (inclusive).initialDrivers: number[]: An array of non-negative integers representing the initial number of available drivers in each zone. initialDrivers[i] corresponds to zone i.zoneIndex: number: The 0-indexed position of the zone to be updated.newCount: number: The new non-negative number of available drivers for the specified zoneIndex.startZone: number: The 0-indexed start of the query range (inclusive).endZone: number: The 0-indexed end of the query range (inclusive).queryTotalAvailable, queryMaxAvailableZone): A non-negative integer representing the total available drivers or the maximum available drivers in the queried range, respectively.constructor, updateDrivers): void (implicitly null in test runner for class methods).zoneIndex, startZone, and endZone within the bounds [0, N-1], where N is the number of zones.startZone will always be less than or equal to endZone for queries.Examples
Example 1
Input:
operations = ["DriverAvailabilityMonitor","queryTotalAvailable","queryMaxAvailableZone","updateDrivers","queryTotalAvailable","queryMaxAvailableZone","updateDrivers","queryTotalAvailable"] params = [[[10,5,20,15]],[0,3],[0,3],[1,25],[0,3],[0,3],[2,8],[1,2]]
Output:
[null,50,20,null,70,25,null,33]
Note:
Example 2
Input:
operations = ["DriverAvailabilityMonitor","queryMaxAvailableZone","updateDrivers","queryTotalAvailable","queryMaxAvailableZone","updateDrivers","queryMaxAvailableZone"] params = [[[1,2,3]],[0,0],[0,10],[0,2],[1,2],[2,0],[0,2]]
Output:
[null,1,null,15,3,null,10]
Note:
Constraints
1 <= N <= 10^5 (where N is the number of zones/length of initialDrivers)0 <= initialDrivers[i] <= 10^40 <= newCount <= 10^40 <= zoneIndex < N0 <= startZone <= endZone < N1 <= total number of operations (constructor, updates, queries) <= 10^5updateDrivers, queryTotalAvailable, and queryMaxAvailableZone should be O(log N).O(N).O(log N) time complexity for operations and O(N) space complexity.Loading editor...