Minimal Waiting Time

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.

Solution
Use a map to store previous total waiting time per index.

Time Complexity: O(n log n)

Space Complexity: O(1)

Algorithm used: Greedy Algorithm

static int getMinimumWaitingTime(int[] queries) {

    /**
     * sort the array to help getting the minimum total waiting time
     */
    Arrays.sort(queries);

    int size = queries.length;

    if (size <= 1) {
        return 0;
    }

    Map<Integer, Integer> map = new HashMap<>();

    int totalWaitingTime = 0;

    for (int i = 0; i < queries.length; i++) {
        int currentWaitingTime = 0;
        int previousTotalWaitingTime = 0;

        if (i != 0) {
            currentWaitingTime = queries[i - 1];
            previousTotalWaitingTime = currentWaitingTime + map.get(i - 1);
        }

        map.put(i, previousTotalWaitingTime);

        totalWaitingTime += previousTotalWaitingTime;

    }

    return totalWaitingTime;
}

 

Source code on Github




Subscribe To Our Newsletter
You will receive our latest post and tutorial.
Thank you for subscribing!

required
required


Leave a Reply

Your email address will not be published.