Livspace Smart Delivery Dispatch
Livspace operates a sophisticated supply chain to ensure timely delivery and installation of home interior solutions. A critical bottleneck is the central dispatch system, which sequences material deliveries and installation teams for various projects. Optimizing this sequence is crucial for client satisfaction and operational efficiency, especially when dealing with varying priorities and geographical zones.
This problem challenges you to design a dispatch algorithm that prioritizes urgent deliveries while strategically grouping tasks for the same geographical zone to minimize travel time and maximize resource utilization. Your solution will simulate the dispatch process and determine the optimal sequence of delivery requests.
Implement the getDispatchSequence function that simulates a delivery dispatch system. Given a list of DeliveryRequest objects, your function should return an array of requestIds in the order they are dispatched.
The dispatch system operates in discrete time steps (e.g., minutes) and processes one request at a time. The selection of the next request follows these rules:
t, only requests with scheduledTime <= t are eligible for dispatch.priority value (e.g., 1 is more urgent than 2).priority, prefer those with the earliest scheduledTime.lastProcessedZone (i.e., lastProcessedZone is not null), and at least one of these top-tier eligible requests is also for lastProcessedZone, then the dispatcher must choose one of these zone-matching requests. If multiple such requests exist, pick the one with the earliest scheduledTime (breaking ties by requestId lexicographically if scheduledTime is also identical).
b. If lastProcessedZone is null (this is the very first task) or if no such zone-matching request exists among the top-tier eligible candidates, then the dispatcher picks the eligible request with the earliest scheduledTime (breaking any remaining ties by requestId lexicographically if scheduledTime is also identical).Once a request is dispatched, it occupies the system for its estimatedCompletionTime. The system then moves to the next time step, considering new eligible requests and the remaining ones.
Input: requests: DeliveryRequest[]
An array of DeliveryRequest objects, where each object has the following structure:
interface DeliveryRequest {
requestId: string; // Unique identifier for the request
priority: number; // Priority level (1 = urgent, 2 = standard, 3 = low)
deliveryZone: number; // Geographical delivery zone (1 to N)
estimatedCompletionTime: number; // Time in minutes required to complete this delivery
scheduledTime: number; // Timestamp (minutes from start) when this request becomes available
}
Output: string[]
An array of requestIds, representing the sequence in which the requests are dispatched by the system.
scheduledTime values are non-negative and can be considered timestamps from the start of the dispatch operation.estimatedCompletionTime values are positive integers.priority values are positive integers, with lower numbers indicating higher priority.deliveryZone values are positive integers.requests array is not necessarily sorted by scheduledTime.scheduledTime to be the same for multiple requests. In such cases, the priority rule applies. If priority and scheduledTime are identical for multiple requests, the requestId can be used for arbitrary tie-breaking (e.g., lexicographically) if the zone rule doesn't apply.Examples
Example 1
Input:
requests = [ { "requestId": "A", "priority": 1, "deliveryZone": 1, "estimatedCompletionTime": 5, "scheduledTime": 0 }, { "requestId": "B", "priority": 1, "deliveryZone": 2, "estimatedCompletionTime": 5, "scheduledTime": 0 }, { "requestId": "C", "priority": 2, "deliveryZone": 1, "estimatedCompletionTime": 5, "scheduledTime": 0 }, { "requestId": "D", "priority": 1, "deliveryZone": 1, "estimatedCompletionTime": 5, "scheduledTime": 10 } ]
Output:
["A","B","D","C"]
Note:
At time 0: A, B, C are eligible. Top candidates are A (P1,Z1,ST0) and B (P1,Z2,ST0). No lastProcessedZone. Arbitrarily pick A (e.g., by requestId). Process A (5min). lastProcessedZone=1. At time 5: B, C are eligible. Top candidate is B (P1,Z2,ST0). Process B (5min). lastProcessedZone=2. At time 10: C, D are eligible. Top candidate is D (P1,Z1,ST10). Process D (5min). lastProcessedZone=1. At time 15: C is eligible. Top candidate is C (P2,Z1,ST0). Process C (5min). lastProcessedZone=1.
Example 2
Input:
requests = [ { "requestId": "X", "priority": 2, "deliveryZone": 5, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "Y", "priority": 1, "deliveryZone": 3, "estimatedCompletionTime": 8, "scheduledTime": 2 }, { "requestId": "Z", "priority": 2, "deliveryZone": 5, "estimatedCompletionTime": 7, "scheduledTime": 1 } ]
Output:
["X","Y","Z"]
Note:
At time 0: Only X is eligible. Process X (10min). lastProcessedZone=5. At time 10: Current time is 10. Y (ST2) and Z (ST1) become eligible. Top candidates are Y (P1,Z3,ST2) and Z (P2,Z5,ST1). Y is higher priority (P1). Process Y (8min). lastProcessedZone=3. At time 18: Current time is 18. Only Z (P2,Z5,ST1) remains eligible. Process Z (7min). lastProcessedZone=5.
Example 3
Input:
requests = [ { "requestId": "P1", "priority": 1, "deliveryZone": 10, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "P2", "priority": 1, "deliveryZone": 10, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "P3", "priority": 2, "deliveryZone": 10, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "Q1", "priority": 1, "deliveryZone": 20, "estimatedCompletionTime": 10, "scheduledTime": 0 }, { "requestId": "Q2", "priority": 2, "deliveryZone": 20, "estimatedCompletionTime": 10, "scheduledTime": 0 } ]
Output:
["P1","P2","Q1","Q2","P3"]
Note:
At time 0: All requests are eligible. Top candidates: P1(P1,Z10,ST0), P2(P1,Z10,ST0), Q1(P1,Z20,ST0). No lastProcessedZone. Pick P1 (arbitrary tie-break among P1, P2, Q1, e.g., by requestId). Process P1 (10min). lastProcessedZone=10. At time 10: Remaining eligible: P2, P3, Q1, Q2. Top candidates: P2(P1,Z10,ST0), Q1(P1,Z20,ST0). lastProcessedZone=10. P2 matches zone. Pick P2. Process P2 (10min). lastProcessedZone=10. At time 20: Remaining eligible: P3, Q1, Q2. Top candidates: Q1(P1,Z20,ST0). Pick Q1. Process Q1 (10min). lastProcessedZone=20. At time 30: Remaining eligible: P3, Q2. Top candidates: P3(P2,Z10,ST0), Q2(P2,Z20,ST0). lastProcessedZone=20. Q2 matches zone. Pick Q2. Process Q2 (10min). lastProcessedZone=20. At time 40: Remaining eligible: P3. Top candidate: P3(P2,Z10,ST0). Pick P3. Process P3 (10min). lastProcessedZone=10.
Constraints
1 <= requests.length <= 1000requestId is unique and consists of alphanumeric characters.1 <= priority <= 51 <= deliveryZone <= 1001 <= estimatedCompletionTime <= 600 (10 hours)0 <= scheduledTime <= 10^5 (large enough to simulate long-running operations)scheduledTime and estimatedCompletionTime are abstract units.O(N log N) where N is the number of requests).scheduledTime values.Loading editor...