Top K Impactful Service Requests
Urban Company processes millions of service requests daily across various verticals. To ensure efficient resource allocation and maintain high customer satisfaction, it's crucial to identify and prioritize the most impactful requests at any given time. This problem simulates a core component of that prioritization system, challenging you to select the most critical tasks from a continuous stream of incoming requests.
You are tasked with implementing a function that identifies the K most impactful service requests from a given list. Each request has a unique ID, a priority score, and an estimated processing time. The "impact" of a request is determined by the following criteria, in descending order of importance:
priority_score: A request with a higher priority score is inherently more impactful.estimated_processing_time: If priority scores are equal, a request with a lower estimated processing time is considered more impactful (as it frees up resources faster).request_id: If both priority scores and estimated processing times are equal, a request with a lower request_id is considered more impactful. This serves as a deterministic tie-breaker.Your function should process a list of ServiceRequest objects and return the request_ids of the K most impactful requests.
Input:
requests: An array of ServiceRequest objects. Each ServiceRequest object has the following structure:
id: number (unique identifier for the request)priority: number (priority score, higher is more urgent)processingTime: number (estimated time in minutes)K: number The number of most impactful requests to identify.Output:
numbers, representing the request_ids of the K most impactful requests. The request_ids in the output array should be sorted in descending order of impact (most impactful first). If two requests have the same impact, their request_ids should be sorted in ascending order. If fewer than K requests are available, return all available request_ids sorted by impact.requests array should result in an empty output array.K will always be a positive integer.request_ids, priority scores, and processingTime values will be non-negative integers. request_ids are guaranteed to be unique.Examples
Example 1
Input:
requests = [ { id: 101, priority: 5, processingTime: 20 }, { id: 102, priority: 8, processingTime: 15 }, { id: 103, priority: 5, processingTime: 10 }, { id: 104, priority: 3, processingTime: 30 } ], K = 2
Output:
[102,103]
Note:
Requests by impact: (102, 8, 15) > (103, 5, 10) > (101, 5, 20) > (104, 3, 30). (102, 8, 15) has highest priority (8). (103, 5, 10) and (101, 5, 20) have same priority (5). (103, 5, 10) has lower processing time (10 vs 20), so it's more impactful. (104, 3, 30) has lowest priority. The top 2 are 102 and 103, sorted by impact.
Example 2
Input:
requests = [ { id: 1, priority: 10, processingTime: 50 }, { id: 2, priority: 10, processingTime: 20 }, { id: 3, priority: 10, processingTime: 40 } ], K = 2
Output:
[2,3]
Note:
All requests have the same priority (10). (2, 10, 20) has the lowest processing time (20). (3, 10, 40) has the next lowest processing time (40). (1, 10, 50) has the highest processing time (50). The top 2 are 2 and 3, sorted by impact (lower processing time first).
Example 3
Input:
requests = [ { id: 500, priority: 7, processingTime: 100 }, { id: 600, priority: 7, processingTime: 100 }, { id: 400, priority: 7, processingTime: 100 } ], K = 2
Output:
[400,500]
Note:
All requests have the same priority (7) and processing time (100).
Tie-breaking by request_id: lower ID is more impactful.
(400, 7, 100) is more impactful than (500, 7, 100), which is more impactful than (600, 7, 100).
The top 2 are 400 and 500, sorted by impact.
Constraints
0 <= requests.length <= 10^51 <= K (if requests.length is 0, then K effectively means 0, resulting in an empty output. If requests.length > 0, then K will not exceed requests.length).1 <= request.id <= 10^91 <= request.priority <= 1001 <= request.processingTime <= 1000K being larger than the number of requests, or all requests having identical impact.Loading editor...