Chairlift Singles Merge
HardOnline Assessment
Simulate a ski lift whose chairs are filled from a main line of groups and topped up from a singles line, for a very long day.
Each chair holds 4 people. The main line is the list pattern of group sizes (each from 1 to 4), repeated repeats times in order, so it holds len(pattern) * repeats groups. Chairs leave one at a time, and each is loaded like this:
- Groups board in line order. The next group boards if it fits in the free seats; as soon as it does not, boarding stops. A group never jumps ahead of a group that did not fit, and a group never splits. (An empty chair always fits the next group.)
- Then the free seats are filled from the singles line, one person per seat, as long as someone is waiting. Any seat left empty is lost.
The singles line starts with singles people. After a chair leaves, if the main line still has groups, arrivals new singles join the singles line; the line holds at most capacity people and anyone beyond that turns away and is gone. (No singles arrive after the chair that takes the last group.) The lift stops after the chair that takes the last main-line group.
For example, with pattern = [3, 2], one chair takes the 3, finds that the 2 does not fit (1 seat left) and takes one single; the next chair takes the 2, then has 2 free seats for singles.
Input: pattern, repeats, singles, capacity, arrivals.
Output: [chairs, empty, turned_away, waiting]: the number of chairs that left, the total number of empty seats on those chairs, the total number of singles who turned away, and the number of singles still waiting after the last chair left.
Example 1
- Input:
- [[3,2,1],2,2,3,1]
- Output:
- [4,0,0,1]
- Explanation
- The main line is 3, 2, 1, 3, 2, 1 and two singles wait. Chair 1 takes the 3; the 2 does not fit, so one single fills the last seat (one single left) and one more arrives (two waiting). Chair 2 takes 2 and 1 and one single, and so on: chair 3 repeats chair 1, and chair 4 takes the last 2 and 1 plus one single. Four chairs leave, no seat is empty, nobody turns away, and one single is left waiting.
Example 2
- Input:
- [[4,1,1],3,0,2,3]
- Output:
- [6,0,9,0]
- Explanation
- The main line is 4, 1, 1, 4, 1, 1, 4, 1, 1 and nobody waits at first. The chairs carry: 4 / 1, 1 and two singles / 4 / 1, 1 and two singles / 4 / 1, 1 and two singles. That is 6 chairs and no empty seat. Three singles arrive after each of the first five chairs (15 in all) but the line holds only 2, so 9 of them turn away and the 6 who got on are the rest. After the last chair nobody is waiting.
Example 3
- Input:
- [[2,1,3],1000000000000,0,4,1]
- Output:
- [2000000000000,1,0,0]
- Explanation
- The line is 2, 1, 3 repeated 1012 times and nobody waits at first. Chair 1 takes 2 and 1 and leaves with one empty seat (no singles yet). One single arrives, so chair 2 takes the 3 and that single. From then on every chair takes exactly the one single that arrived, and the situation repeats every two chairs. Simulating 3 x 1012 groups is impossible; the state (position in the pattern, singles waiting) repeats quickly, so whole cycles can be skipped. The answer is 2 x 1012 chairs, 1 empty seat in total, nobody turned away and nobody waiting.
Constraints
- 1 ≤ pattern.length ≤ 40; every group size is between 1 and 4
- 1 ≤ repeats ≤ 1012
- 0 ≤ singles ≤ capacity ≤ 60; 0 ≤ arrivals ≤ 8