## Algorithm

Problem Name: Data Structures - Minimum Average Waiting Time

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

Copy The Code &

### #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 vi;
typedef vector vl;
typedef vector vvl;
typedef vector vvi;
typedef vector vd;
typedef pair pll;
typedef pair pii;
typedef pair pdd;
typedef vector vll;
typedef vector 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 q;
ll t = v.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 &

### #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> ordersByTime) {
PriorityQueue waitingCustomers = new PriorityQueue<>();
long currTime = 0;
long totalWaitTime = 0;

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

private static class Customer implements Comparable {
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> 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);
}
}
}

Copy The Code &

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

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

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

const priorityQueue = new PriorityQueue();
let elapsedTime = customers;
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();
}

Copy The Code &

### #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
loop = True
while loop :
while len(allOrders) != 0 and allOrders <= currentTime :
order = heapq.heappop(allOrders)
heapq.heappush(pendingOrders, (order, order))
if len(pendingOrders) != 0 :
minWaitOrder = heapq.heappop(pendingOrders)
waitTime = currentTime - minWaitOrder + minWaitOrder
totalWaitTime += waitTime
currentTime += minWaitOrder
else :
currentTime += 1
if len(pendingOrders) == 0 and len(allOrders) == 0 :
loop = False