Shuttle Seat Plan

Medium

A shuttle drives along a straight road, only forward from mark 0, and has seats passenger seats. You get a list of bookings rides: booking [people, a, b] means a group of people riders must be picked up at mark a and dropped off at mark b. At any mark, riders getting off leave before new riders get on. Return True if the shuttle can serve every booking without ever exceeding its seats, and False otherwise.

Example 1

rides=[[3, 0, 4], [2, 2, 6], [1, 4, 8]], seats=5 → True

Between 2 and 4 there are 3 + 2 = 5 riders, exactly the number of seats. At 4 the first group leaves and the third gets on: 2 + 1 = 3. Everyone fits.

Example 2

rides=[[3, 0, 4], [2, 2, 6], [1, 4, 8]], seats=4 → False

Between 2 and 4 there are 5 riders but only 4 seats.

Constraints

1 ≤ len(rides) ≤ 10⁵
rides[i] = [people, a, b]
1 ≤ people ≤ 100
0 ≤ a < b ≤ 10⁴
1 ≤ seats ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Prefix Sum Sorting Simulation Heap (Priority Queue)

Similar problems

Studios for Recording Sessions Medium K-th Largest Corner XOR Medium Three Heaviest Diamonds Medium Fewest Rooms for the Bookings Medium Cross Out the Smallest First Medium

Input

rides=[[3, 0, 4], [2, 2, 6], [1, 4, 8]], seats=5

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 113 tests on the server, hidden ones included.