All problems

Ferry Car Trips

Easy · queue

Cars wait in a single line to cross a river on a small ferry. Car i is lengths[i] metres long, and the cars are listed in the order they stand in the line (car 0 is at the front). The ferry deck is deck metres long.

The ferry makes one crossing at a time. For each crossing it loads cars from the front of the line, one after another, for as long as the next car in the line still fits in the deck length that is left. The ferry never skips a car: as soon as the next car does not fit, the crossing begins. The cars on board cross, and the ferry comes back empty for the next crossing.

Number the crossings 1, 2, 3 and so on. Return a list with one number per car, in the same order as lengths: the number of the crossing on which that car travels.

Examples

Example 1

Input: lengths = [4, 3, 5, 2, 6], deck = 8

Output: [1, 1, 2, 2, 3]

Cars 0 and 1 fill 7 metres, and car 2 (5 metres) no longer fits. Cars 2 and 3 fill 7 metres and car 4 (6 metres) does not fit, so it crosses alone.

Example 2

Input: lengths = [5, 5, 5], deck = 5

Output: [1, 2, 3]

Every car fills the whole deck, so each one needs its own crossing.

Example 3

Input: lengths = [1, 2, 3], deck = 10

Output: [1, 1, 1]

Constraints