Daily Challenge #162 - Taxi Dispatching

Setup:

You work as a taxi dispatcher. People will contact you to order a taxi, informing you of their pickup and drop-off times. Taxis can only service one customer at a time. They can pick up a new customer 1 time unit after it has dropped off a previous customer. What is the minimum number of taxis you need to service all requests?

Constraints:
Let N be the number of customer requests:
N is an integer in the range [1, 100k]
All times will be integers in range [1, 10k]
Let PU be the time of pickup and DO be the time of drop-off
For each request: PU < DO
The input list is NOT sorted.

Examples:

Two customers, overlapping schedule. Two taxis needed.
requests = [(1, 4), (2, 6)]
min_num_taxis(requests) # => 2

Two customers, no overlap in schedule. Only one taxi needed.
requests = [(1, 4), (5, 9)]
min_num_taxis(requests) # => 1

Tests:

1: [(1,4)]
2: [(1,4), (5, 9)]
3: [(1,4), (2, 9), (3, 6), (5, 8)]

Good luck and have fun!

---

This challenge comes from Scopula on CodeWars. Thank you to CodeWars, who has licensed redistribution of this challenge under the 2-Clause BSD License!

Want to propose a challenge idea for a future post? Email [e-mail] with your suggestions!

Comments

[sarah4594]

My solution in Typescript

export const min_num_taxis = (requests: number[][]): number => {
  const taxis: number[] = []
  // sort by dropoff time
  requests.sort((reqA, reqB) => reqA[1] - reqB[1])
  requests.forEach(request => {
    const [pickup, dropoff] = request
    let foundTaxi = false
    for (let taxi = 0; taxi <= taxis.length; taxi++) {
      if (pickup > taxis[taxi]) {
        foundTaxi = true
        taxis[taxi] = dropoff
      }
    }
    if (!foundTaxi) {
      taxis.push(dropoff)
    }
  })
  return taxis.length
}

and tests

import { min_num_taxis } from '.'

describe('min_num_taxis', () => {
  it('should return the number of taxis needed per request', () => {
    expect(min_num_taxis([[1, 4]])).toBe(1)
    expect(min_num_taxis([[5, 9], [1, 4]])).toBe(1)
    expect(min_num_taxis([[1, 4], [2, 9], [3, 6], [5, 8] ])).toBe(3)
  })
})

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