# HackerRank Minimum Average Waiting Time problem solution

In this HackerRank Minimum Average Waiting Time problem, we have given the number of customers and the time when the customer order a pizza. and the time required to cook that pizza. we need to print or calculate the minimum average waiting time required to arrive at the pizza.

## Problem solution in 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

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)))```

## Problem solution in Java Programming.

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

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

while (!ordersByTime.isEmpty() || !waitingCustomers.isEmpty()) {
if (waitingCustomers.isEmpty()) {
Entry<Long, List<Customer>> firstEntry = ordersByTime.pollFirstEntry();
currTime = firstEntry.getKey();
} else {
Customer nextToCook = waitingCustomers.poll();
currTime += nextToCook.cookTime;
totalWaitTime += currTime - nextToCook.arrivalTime;
NavigableMap<Long, List<Customer>> arrivals = ordersByTime.headMap(currTime, true);
arrivals.values()
.stream()
arrivals.clear();
}
}
}

private static class Customer implements Comparable<Customer> {
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<Customer>> ordersByTime = new TreeMap<>();
for (int i = 0; i < n; i++) {
Customer customer = new Customer(in.nextInt(), in.nextInt());
ordersByTime.computeIfAbsent(customer.arrivalTime,
a -> new ArrayList<>())
}
System.out.println(computeMinAvg(ordersByTime) / n);
}
}
}```

## Problem solution in 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;
}```

## Problem solution in 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 tt = 0;
long tt1 = 0;
while (zap < n || hs) {
while (zap < n && zas[zap].when <= next_ready) {
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) {
} 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);
}
}
fprintf(stderr, "%ld %ld\n", tt, tt1);
if (tt1 != tt) exit(-1);
printf("%ld\n", tt / n);
return 0;
}```

## Problem solution in 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();
});

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;
}

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;
}

this.priorities.set(item, priority);

}

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;
}

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);

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();
}```