Algorithm

Problem Name: Data Structures - Minimum Average Waiting Time

Problem Link: https://www.hackerrank.com/challenges/minimum-average-waiting-time/problem?isFullScreen=true

In this HackerRank in Data Structures - Minimum Average Waiting Time solutions

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes.

Different kinds of pizzas take different amounts of time to cook. Also, once he starts cooking a pizza, he cannot cook another pizza until the first pizza is completely cooked. Let's say we have three customers who come at time t=0, t=1, & t=2 respectively, and the time needed to cook their pizzas is 3, 9, & 6 respectively. If Tieu applies first-come, first-served rule, then the waiting time of three customers is 3, 11, & 16 respectively. The average waiting time in this case is (3 + 11 + 16) / 3 = 10. This is not an optimized solution. After serving the first customer at time t=3, Tieu can choose to serve the third customer. In that case, the waiting time will be 3, 7, & 17 respectively. Hence the average waiting time is (3 + 7 + 17) / 3 = 9.

Help Tieu achieve the minimum average waiting time. For the sake of simplicity, just find the integer part of the minimum average waiting time.

Input Format

  • The first line contains an integer N, which is the number of customers.

  • In the next N lines, the ith line contains two space separated numbers Ti and Li. Ti is the time when ith customer order a pizza, and Li is the time required to cook that pizza.

  • The

customer is not the customer arriving at the

  • arrival time.

Output Format

  • Display the integer part of the minimum average waiting time.

Constraints

  • 1 ≤ N ≤ 105
  • 0 ≤ Ti ≤ 109
  • 1 ≤ Li ≤ 109

Note

  • The waiting time is calculated as the difference between the time a customer orders pizza (the time at which they enter the shop) and the time she is served.

  • Cook does not know about the future orders.

Sample Input #00

3
0 3
1 9
2 6

Sample Output #00

9

Sample Input #01

3
0 3
1 9
2 5

Sample Output #01

8

Explanation #01

Let's call the person ordering at time = 0 as A, time = 1 as B and time = 2 as C. By delivering pizza for A, C and B we get the minimum average wait time to be

(3 + 6 + 16)/3 = 25/3 = 8.33

the integer part is 8 and hence the answer.

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

struct za {
    int when;
    int how_long;
};

int ctime(const void* a_in, const void* b_in) {
    const struct za* a = a_in;
    const struct za* b = b_in;
    if (a->when  <  b->when) return -1;
    if (a->when > b->when) return 1;
    return 0;
}

int za_cmp(struct za a, struct za b) {
    if (a.how_long  <  b.how_long) return -1;

    if (a.how_long > b.how_long) return 1;
    return 0;
}
void insert_heap_lt(struct za* root, int size) {
    int child = size - 1;
    int parent = (child - 1)/2;
    while (child > 0 && za_cmp(root[child], root[parent])  <  0) {
        struct za tmp = root[child];
        root[child] = root[parent];
        root[parent] = tmp;
        child = parent;
        parent = (child - 1)/2;
    }
}

struct za pop_heap_lt(struct za* root, int size) {
    struct za result = root[0];
    root[0] = root[size - 1];
    int parent = 0;
    int child = 1;
    while (child  <  size - 1) {
        int c2 = child + 1;
        if (c2 < size - 1 && za_cmp(root[c2], root[child]) < 0) {
            child = c2;
        } 
        if (za_cmp(root[child], root[parent])  <  0) {
            struct za tmp = root[child];
            root[child] = root[parent];
            root[parent] = tmp;
            parent = child;
            child = 2 * parent + 1;
        } else break;
    }
    return result;
}

int main() {
    int n;
    scanf("%d\n", &n);
    struct za zas[n];
    struct za zash[n];
    int hs = 0;
    for (int i = 0; i  <  n; i++) {
        scanf("%d %d\n", &zas[i].when, &zas[i].how_long);
    }
    qsort(zas, n, sizeof(struct za), ctime);
    int zap = 0;
    long next_ready = zas[zap].when;
    long tt = 0;
    long tt1 = 0;
    while (zap  <  n || hs) {
        while (zap < n && zas[zap].when <= next_ready) {
            tt1 += next_ready - zas[zap].when;
            zash[hs++] = zas[zap];
            fprintf(stderr, "push: %d %d\n", zas[zap].when, zas[zap].how_long);
            insert_heap_lt(zash, hs);
            zap++;
        }
        if (!hs) {
            next_ready = zas[zap].when;
        } else {
            struct za cookme = pop_heap_lt(zash, hs--);
            tt1 += cookme.how_long * ((long)hs + 1);
          fprintf(stderr, "pop: %d %d\n", cookme.when, cookme.how_long);
            next_ready = next_ready + cookme.how_long;
            tt += next_ready - cookme.when;
        }
    }
    fprintf(stderr, "%ld %ld\n", tt, tt1);
    if (tt1 != tt) exit(-1);
    printf("%ld\n", tt / n);
    return 0;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <iostream>
#include <set>
#include <vector>
#include <cstring>
#include <string>
#include <algorithm>
#include <numeric>
#include <cmath>
#include <complex>
#include <map>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector < ll> vl;
typedef vector<vl> vvl;
typedef vector < vi> vvi;
typedef vector<double> vd;
typedef pair < ll, ll> pll;
typedef pair<int, int> pii;
typedef pair < double, double> pdd;
typedef vector<pll> vll;
typedef vector < string> vs;

int main() {
    int n;
    cin >> n;
    vll v(n);
    for (int i = 0; i  <  n; ++i) {
        scanf("%lld%lld", &v[i].first, &v[i].second);        
    }
    sort(v.begin(), v.end());
    ll sum = 0;
    set < pii> q;
    ll t = v[0].first;
    int it = 0;
    while (it  <  n || q.size()) {
        while (it < n && v[it].first <= t) {
            q.insert(pii(v[it].second, it));
            ++it;
        }
        if (q.empty()) {
            t = v[it].first;
        } else {
            int i = q.begin()->second;
            q.erase(q.begin());
            t += v[i].second;
            sum += t-v[i].first;
        }
    }
    cout << sum / n << endl;
    return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;
import java.util.Map.Entry;

public class Solution {
    private static long computeMinAvg(NavigableMap < Long, List waitingCustomers = new PriorityQueue<>();
        long currTime = 0;
        long totalWaitTime = 0;

        while (!ordersByTime.isEmpty() || !waitingCustomers.isEmpty()) {
            if (waitingCustomers.isEmpty()) {
                Entry < Long, List {
        final long arrivalTime;
        final Long cookTime;

        Customer(long arrivalTime, long cookTime) {
            this.arrivalTime = arrivalTime;
            this.cookTime = cookTime;
        }

        @Override
        public int compareTo(Customer o) {
            return cookTime.compareTo(o.cookTime);
        }
    }

    public static void main(String[] args) {
        try (Scanner in = new Scanner(System.in)) {
            int n = in.nextInt();

            NavigableMap < Long, List();
            for (int i = 0; i  <  n; i++) {
                Customer customer = new Customer(in.nextInt(), in.nextInt());
                ordersByTime.computeIfAbsent(customer.arrivalTime,
                                             a -> new ArrayList < >())
                            .add(customer);
            }
            System.out.println(computeMinAvg(ordersByTime) / n);
        }
    }
}
Copy The Code & Try With Live Editor

#4 Code Example with Javascript Programming

Code - Javascript Programming


'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', inputStdin => {
    inputString += inputStdin;
});

process.stdin.on('end', _ => {
    inputString = inputString.trim().split('\n').map(str => str.trim());

    main();
});

function readLine() {
    return inputString[currentLine++];
}

class Heap {
    constructor() {
        this.data = [];
        this.length = 0;
    }

    getChild(parent) {
        const left = Math.floor(parent * 2) + 1;
        const right = left + 1;

        if (right  <  this.length - 1 && this.isOrdered(left, right)) {
            return right;
        }

        if (left < this.length - 1) {
            return left;
        }
    }

    swapNode(source, destination) {
        const temp = this.data[source];

        this.data[source] = this.data[destination];
        this.data[destination] = temp;
    }

    isOrdered(current, parent) {
        if (this.data[current] > this.data[parent]) {
            return true;
        }

        return false;
    }

    add(value) {
        this.data.push(value);

        this.length += 1;

        let current = this.length - 1;

        while (current > 0) {
            const parent = Math.floor((current - 1) / 2);

            if (this.isOrdered(current, parent)) {
                break;
            }

            this.swapNode(current, parent);

            current = parent;
        }
    }
    
    remove(index) {
        if (index  <  0 && index >= this.length) {
            return;
        }

        const deleted = this.data[index];

        if (this.length > 1) {
            this.data[index] = this.data.pop();
        } else {
            this.data = [];
        }

        let current = index;
        while (current  <  this.length) {
            const child = this.getChild(current);

            if (!child || this.isOrdered(child, current)) {
                break;
            }

            this.swapNode(current, child);

            current = child;
        }

        this.length -= 1;

        return deleted;
    }

    pop() {
        return this.data[this.length - 1];
    }

    poll() {
        return this.remove(0);
    }
}

class PriorityQueue extends Heap {
    constructor() {
        super();

        this.priorities = new Map();
        
        this.isOrdered = this.comparePriority;
    }

    add(item, priority = 0) {
        this.priorities.set(item, priority);

        super.add(item);
    }

    poll() {
        const item = super.poll();

        this.priorities.delete(item);

        return item;
    }

    comparePriority(target, source) {
        const a = this.priorities.get(this.data[target]);
        const b = this.priorities.get(this.data[source]);

        return (a > b) ? true : false;
    }
}

const compareArrivalTime = (a, b) => a[0] - b[0];

/*
 * Complete the minimumAverage function below.
 */
function minimumAverage(customers) {
    customers.sort(compareArrivalTime);

    const priorityQueue = new PriorityQueue();
    let elapsedTime = customers[0][0];
    let waitingTime = 0;
    let next = 0;

    customers.forEach(customer => {
        while (next  <  customers.length) {
            const [ arrivalTime, requiredTime ] = customers[next];

            if (arrivalTime > elapsedTime && priorityQueue.length > 0) {
                break;
            }

            priorityQueue.add(customers[next], requiredTime);

            next += 1;
        }

        const [arrivalTime, requiredTime] = priorityQueue.poll();
        elapsedTime += requiredTime;
        waitingTime += elapsedTime - arrivalTime;
    });

    return Math.floor(waitingTime / customers.length);
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const n = parseInt(readLine(), 10);

    let customers = Array(n);

    for (let customersRowItr = 0; customersRowItr  <  n; customersRowItr++) {
        customers[customersRowItr] = readLine().split(' ').map(customersTemp => parseInt(customersTemp, 10));
    }

    let result = minimumAverage(customers);

    ws.write(result + "\n");

    ws.end();
}
Copy The Code & Try With Live Editor

#5 Code Example with Python Programming

Code - Python Programming


import heapq

def minWait(allOrders) :
    totalWaitTime = 0
    numOrders = len(allOrders)
    if numOrders == 0 :
        return 0
    pendingOrders = []
    currentTime = allOrders[0][0]
    loop = True
    while loop :
        while len(allOrders) != 0 and allOrders[0][0] <= currentTime :
            order = heapq.heappop(allOrders)   
            heapq.heappush(pendingOrders, (order[1], order[0]))
        if len(pendingOrders) != 0 :
            minWaitOrder = heapq.heappop(pendingOrders)
            waitTime = currentTime - minWaitOrder[1] + minWaitOrder[0]
            totalWaitTime += waitTime
            currentTime += minWaitOrder[0]
        else :
            currentTime += 1
        if len(pendingOrders) == 0 and len(allOrders) == 0 :
            loop = False
    return totalWaitTime/numOrders

n = int(input())
allOrders = []
for i in range(n) :
    line = input().split()
    l, t = int(line[0]), int(line[1])
    heapq.heappush(allOrders, (l, t))
print (int(minWait(allOrders)))
Copy The Code & Try With Live Editor
Advertisements

Demonstration

Previous
[Solved] Find the Running Median solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Truck Tour solution in Hackerrank - Hacerrank solution C, C++, java,js, Python