Discussion on: Daily Challenge #126 - The Supermarket Line

use std::collections::BinaryHeap;
use std::cmp::Reverse;

fn queue_time(customers: &[usize], n: usize) -> usize {
    assert!(0 < n, "can't serve anyone without registers");

    let mut customers = customers.iter().copied().fuse();

    // The first n customers start at 0 and finish at their serving time.
    let mut finish_times: BinaryHeap<_> = customers.by_ref().take(n).map(Reverse).collect();

    for serving_time in customers {
        // `finish_times.pop()` returns the next time a customer finishes.
        let Reverse(current_time) = finish_times.pop()
            .expect("finish_times should not be empty here - we add a new entry for each one we take");
        // This register was cleared at `current_time`, and will be cleared again after
        // serving_time passes.
        finish_times.push(Reverse(current_time + serving_time));
    }

    // No more pending customers - so just wait for the last one in the registers.
    finish_times.drain().map(|Reverse(time)| time).max()
        // `finish_times` can only be empty if customers was empty to begin with.
        .unwrap_or(0)
}

fn main() {
    assert_eq!(queue_time(&[5,3,4], 1), 12);
    assert_eq!(queue_time(&[10,2,3,3], 2), 10);
    assert_eq!(queue_time(&[2,3,10], 2), 12);
}