Discussion on: Daily Challenge #162 - Taxi Dispatching

[Idan Arye]

Rust:

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

fn num_taxis_required(requests: &[(usize, usize)]) -> usize {
    let mut pending = requests.iter().cloned().map(Reverse).collect::<BinaryHeap<_>>();
    let mut ongoing = BinaryHeap::new();
    let mut max_concurrent_drives = 0;
    for Reverse((start, end)) in pending.drain() {
        while let Some(Reverse(frees_at)) = ongoing.peek() {
            if *frees_at <= start {
                ongoing.pop();
            } else {
                break;
            }
        }
        ongoing.push(Reverse(end + 1));
        max_concurrent_drives = max_concurrent_drives.max(ongoing.len());
    }
    max_concurrent_drives
}

fn main() {
    assert_eq!(num_taxis_required(&[(1,4)]), 1);
    assert_eq!(num_taxis_required(&[(1,4), (5, 9)]), 1);
    assert_eq!(num_taxis_required(&[(1,4), (2, 9), (3, 6), (5, 8)]), 3);
}