TheAlgorithms-Python

1
"""
2
Calculate the minimum waiting time using a greedy algorithm.
3
reference: https://www.youtube.com/watch?v=Sf3eiO12eJs
4

5
For doctests run following command:
6
python -m doctest -v minimum_waiting_time.py
7

8
The minimum_waiting_time function uses a greedy algorithm to calculate the minimum
9
time for queries to complete. It sorts the list in non-decreasing order, calculates
10
the waiting time for each query by multiplying its position in the list with the
11
sum of all remaining query times, and returns the total waiting time. A doctest
12
ensures that the function produces the correct output.
13
"""
14

15

16
def minimum_waiting_time(queries: list[int]) -> int:
17
    """
18
    This function takes a list of query times and returns the minimum waiting time
19
    for all queries to be completed.
20

21
    Args:
22
        queries: A list of queries measured in picoseconds
23

24
    Returns:
25
        total_waiting_time: Minimum waiting time measured in picoseconds
26

27
    Examples:
28
    >>> minimum_waiting_time([3, 2, 1, 2, 6])
29
    17
30
    >>> minimum_waiting_time([3, 2, 1])
31
    4
32
    >>> minimum_waiting_time([1, 2, 3, 4])
33
    10
34
    >>> minimum_waiting_time([5, 5, 5, 5])
35
    30
36
    >>> minimum_waiting_time([])
37
    0
38
    """
39
    n = len(queries)
40
    if n in (0, 1):
41
        return 0
42
    return sum(query * (n - i - 1) for i, query in enumerate(sorted(queries)))
43

44

45
if __name__ == "__main__":
46
    import doctest
47

48
    doctest.testmod()
49