Header Ad

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.

HackerRank Minimum Average Waiting Time problem solution


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


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();
                waitingCustomers.addAll(firstEntry.getValue());
                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()
                        .forEach(waitingCustomers::addAll);
                arrivals.clear();
            }
        }
        return totalWaitTime;
    }

    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<>())
                            .add(customer);
            }
            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 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;
}


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

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


Post a Comment

0 Comments