Order Queries by Shortest Processing Time
Scale AI● MediumNEW GRADPHONE SCREENProblem statement
Given queryIntervals, return the original query indices in an order that minimizes the sum of query completion times.
For this exercise, assume an interval [start,end] describes a query whose processing duration is end-start. The endpoints do not constrain its start time. All queries are available at processing time 0, and one worker processes one whole query at a time without preemption or idle gaps.
The completion time of a query is the total duration of that query and every query before it in the chosen order. If multiple optimal orders differ only in queries with equal durations, place their original indices in ascending order.
Return every zero-based index exactly once. An empty input returns an empty array. The interval data has already been obtained from the supplied input interface; no model or network call is required.
Function
queryProcessingOrder(queryIntervals: int[][]) → int[]Examples
Example 1
queryIntervals = [[0,3],[10,11],[2,4]]return = [1,2,0]The durations are 3, 1, and 2. The returned order completes queries at times 1, 3, and 6, with total completion time 10.
Example 2
queryIntervals = [[5,7],[0,2],[9,11]]return = [0,1,2]All durations are 2, so every order has the same objective. The required ascending-index tie rule selects 0, 1, 2.
Example 3
queryIntervals = []return = []There are no queries to schedule, so the order is empty.
Constraints
- For this exercise, assume
0 <= queryIntervals.length <= 100000. - Every row contains two integers with
0 <= start < end <= 1000000000. - Rows may be unsorted, overlapping, nested, or identical; every row is a separate query.