DEV Community

dev.to staff
dev.to staff

Posted on

Daily Challenge #162 - Taxi Dispatching

#challenge

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!

Top comments (2)

Collapse
 
sarah4594 profile image
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) }) })
Collapse
 
idanarye profile image
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); }