dev.to staff

Posted on

# 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 yo+challenge@dev.to with your suggestions!

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