Minimum Waiting Time

Tags

Minimum Waiting Time

Category

Greedy

Difficulty

Easy

Problem Statement

Given a non-empty array of positive integers representing the durations of queries that need to be executed, find the minimum total waiting time for all queries. Only one query can be executed at a time, but they can be executed in any order. A query's waiting time is the total time it must wait before its execution begins (not including its own execution time).

Intuition

Shorter queries should be executed first because each query's duration contributes to the waiting time of all subsequent queries. A query at position i adds its duration to the waiting time of all n - i - 1 queries that come after it. By sorting in ascending order, we ensure that the durations contributing to the most waiting times are as small as possible, minimizing the total.

Approach

  1. Sort the array of query durations in ascending order.
  2. Initialize totalWaitingTime = 0.
  3. For each query at index i:
    • The number of queries that must wait because of this query is n - i - 1.
    • Add durations[i] * (n - i - 1) to totalWaitingTime.
  4. Return totalWaitingTime.

Pseudocode

function minimumWaitingTime(queries):
    sort(queries)  // ascending order
    totalWaitingTime = 0
    n = length(queries)

    for i from 0 to n - 1:
        queriesLeft = n - (i + 1)
        totalWaitingTime = totalWaitingTime + queries[i] * queriesLeft

    return totalWaitingTime

Time & Space Complexity

  • Time: O(n log n) dominated by the sorting step. The subsequent iteration is O(n).
  • Space: O(1) if sorting is done in-place (ignoring the space used by the sorting algorithm itself).

Key Insights

  • This is a classic greedy problem: the globally optimal solution is achieved by the locally optimal strategy of always running the shortest remaining query next.
  • The greedy choice can be proven optimal by an exchange argument: swapping a longer query before a shorter one always increases total waiting time.
  • The first query in the sorted order has zero waiting time. The last query contributes nothing to other queries' waiting times.

Edge Cases

  • Single query: the waiting time is 0 (no query waits for it).
  • All queries have the same duration: the order does not matter, but the formula still works.
  • Array already sorted: sorting is a no-op, but the algorithm still processes correctly.
  • Two queries: the shorter one should go first, and the waiting time equals the shorter duration.

Linked mentions