---
# System prepended metadata

title: '#1 Greedy Algorithm: Minimum Waiting Time'
tags: [Easy, Greedy Algorithm]

---

# #1 Greedy Algorithm: Minimum Waiting Time

###### tags:`Greedy Algorithm` `Easy`

<br>

## Issue

You're given a non-empty array of positive integers representing the amounts 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 durations 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 the duration of the first two queries before being executed.

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


### Sample Input

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

### Sample Output

```javascript=
17
```

### Hints
:::spoiler Hint 1
Even though you don't need to return the actual order in which the queries will be executed to minimize the total waiting time, it's important to determine what this order should be. Start by doing so.
:::

:::spoiler Hint 2
Can you solve this problem with constant space? What advantage does being able to mutate the input array provide?
:::

:::spoiler Hint 3
Sort the input array in place, and execute the shortest queries in their sorted order. This should allow you to calculate the minimum waiting time.
:::

:::spoiler Hint 4
Create a variable to store the total waiting time, and iterate through the sorted input array. At each iteration, multiply the number of queries left by the duration of the current query, and add that to the total waiting time.
:::

### Optimal Space & Time Complexity

:::spoiler Answer
O(nlogn) time | 0(1) space - where n is the number of queries
:::

<br>

## Solutions

### Official

:::spoiler Solution 1
```javascript=
// O(nlogn) time 0(1) space - where n is the number of queries

function minimumWaitingTime (queries) {
  queries.sort((a, b) => a - b);

  let totalWaitingTime = 0;
  for (let idx = 0; idx < queries.length; idx++) {
  const duration = queries[idx];
  const queriesLeft = queries.length - (idx + 1);
  totalWaitingTime += duration * queriesLeft;
  }

  return totalWaitingTime;
}
```
:::

### Everyone's

:::spoiler 東
```javascript=
// Time O(nlogn), space O(1) | O is the number of queries 
function minimumWaitingTime(queries) {
  queries.sort((a, b) => a - b);
  let waitingTime = 0;
  let totalWaitingTime = 0;
  for(let i = 0 ; i < queries.length - 1; i++){
    waitingTime += queries[i];
    totalWaitingTime += waitingTime;
  }
  return totalWaitingTime;
}
```
:::

<br>

:::spoiler Hao
```javascript=
/**
 * Time complexity: O(nlogn) where n stands for the number of querys
 * Space complexity: O(1)
 */

function minimumWaitingTime(queries) {
  let sum = 0;
  const queryOrder = queries.sort((a, b) => a - b);
  queryOrder.forEach((time, idx) => {
    const nWaitTheTime = queryOrder.length - idx - 1;
    sum += time * nWaitTheTime;
  })
  return sum;
}
```
:::

<br>

:::spoiler YC
```javascript=
//time: O(nlogn), space: O(1) - where n is the length of the given array
function minimumWaitingTime(queries) {
  if (queries.length <= 1) return 0;
  
  let sum = 0;
  let currSum = 0;
  queries.sort((a,b) => a-b);
  for (let i = 1; i < queries.length; i++){
    currSum += queries[i-1];
    sum += currSum;
  }
  return sum;

}
```
:::

<br>

:::spoiler Becky
```javascript=
```
:::

<br>

:::spoiler 月薪
```javascript=
/*
Time: O(nlogn), where n is the length of queries
Space: O(1)
*/
function minimumWaitingTime(queries) {
  queries.sort((a,b) => a - b);
  const { length } = queries;
  return queries.reduce((a,b,idx) => a + b * (length - (idx + 1)), 0)
}
```
:::

<br>

## Discussion
**Time complexity is O(NlogN) instead of O(N)**
It is because we should `sort` the list first.
