Minimum Waiting Time with Time and Space Complexity — Competitive Programming

Question

You’re given a non-empty array of positive integers representing the amount of time that specific queries take to execute. Only one query can be executed at a time, but the queries can be executed in any order.

A query’s waiting time is defined as the amount of time that it must wait before its execution starts. In other words, if a query is executed second, then its waiting time is the duration of the first query; if a query is executed third, then its waiting time is the sum of the duration of the first two queries.

Write a function that returns the minimum amount of total waiting time for all of the queries. For example, if you’re given the queries of durations [1, 4, 5], then the total waiting time if the queries were executed in the order of [5, 1, 4] would be (0) +(5) + (5 + 1) = 11. The first query of duration 5 would be executed immediately, so its waiting time would be 0, the second query of duration 1 would have to wait 5 seconds (the duration of the first query) to be executed, and the last query would have to wait for the duration of the first two queries before being executed.

Note: you’re allowed to mutate the input array.

Sample Input:

queries = [3, 2, 1, 2, 6]

Sample Output:

17

Solution

private int MinWaitingTime(int[] queries)
{
// Time Complexity - O(n logn)
// Space Complexity - O(1)
Array.Sort(queries);
int sum = 0;
int waitingTime = 0;
// Waiting time of first query is always 0
for (int i = 0; i < queries.Length - 1; i++)
{
waitingTime += queries[i];
sum += waitingTime;
}
return sum;
}

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store