路口等待时间

题目描述

十字路口的红绿灯分为东西向（E/W）和南北向（S/N）两组，两组状态始终相反。东西向红灯亮 $R$ 秒，然后绿灯亮 $G$ 秒，不断循环；南北向则相反——绿灯亮 $R$ 秒，然后红灯亮 $G$ 秒。刚开始时（$0$ 秒）东西方向是红灯，南北方向是绿灯。

红绿灯切换无过渡期，红灯结束时绿灯立即开始，无需额外等待。

车辆到达路口时，遇到绿灯直接走，通过路口需要 $1$ 秒，如遇到红灯停下来等。E/W/S/N 四个方向各有一条独立车道，各自排队，互不干扰，而同向后车必须等前车走完才能走。

求从第一辆车到达路口，到最后一辆车完全离开，共同花费多少秒，和最后一辆离开的时间是第几秒。

函数接口

请实现以下函数：

// C++
class Solution {
public:
    vector<int> intersectionWaitingTime(int R, int G, vector<char>& directions, vector<int>& arrivalTimes);
};

// Java
class Solution {
    public int[] intersectionWaitingTime(int R, int G, char[] directions, int[] arrivalTimes);
}

# Python
class Solution:
    def intersectionWaitingTime(self, R: int, G: int, directions: List[str], arrivalTimes: List[int]) -> List[int]:

// JavaScript
/**
 * @param {number} R
 * @param {number} G
 * @param {string[]} directions
 * @param {number[]} arrivalTimes
 * @return {number[]}
 */
var intersectionWaitingTime = function(R, G, directions, arrivalTimes) { ... };

// C
/**
 * @param R 东西向红灯时长
 * @param G 东西向绿灯时长
 * @param directions 方向字符数组（'E','W','S','N'）
 * @param directionsSize 方向数组长度
 * @param arrivalTimes 到达时间数组
 * @param arrivalTimesSize 到达时间数组长度
 * @param returnSize 传出结果数组长度
 * @return 长度为2的数组 [总耗时, 最后一辆离开的时间]
 */
int* intersectionWaitingTime(int R, int G, char* directions, int directionsSize,
                             int* arrivalTimes, int arrivalTimesSize, int* returnSize);

参数说明

返回值

返回一个长度为 $2$ 的整数数组 [totalTime, lastSecond]：

• totalTime：第一辆车到达路口到最后一辆车完全离开的总耗时（秒）
• lastSecond：最后一辆车离开的时刻（秒）

约束

• $1 \leq R, G \leq 60$
• $0 \leq \text{arrivalTimes}[i] \leq 100$
• $1 \leq \text{车辆数量} \leq 100$
• 车辆按照到达时间的非递减顺序给出
• 方向数组长度与到达时间数组长度相等

样例

样例 1

输入：

3,5,[E,S,W,N],[0,1,3,6]

输出：

[9,9]

解释：

周期 $C = R + G = 8$ 秒。

• E/W 方向红灯条件：$t \bmod 8 < 3$，绿灯条件：$t \bmod 8 \geq 3$
• S/N 方向红灯条件：$t \bmod 8 \geq 3$，绿灯条件：$t \bmod 8 < 3$

所有车辆都在同个 $C$ 周期内：

• E 车 $0$ 秒到达：$0 < R$ 红灯，等 $3$ 秒至 $t=3$ 开始通行，$t=4$ 离开（通行需 $1$ 秒）
• S 车 $1$ 秒到达：直接绿灯通过，$t=1$ 开始，$t=2$ 离开
• W 车 $3$ 秒到达：$R=3$，第 $3$ 秒已是绿灯，$t=3$ 开始，$t=4$ 离开
• N 车 $6$ 秒到达：$6 \geq 3$ 红灯，需等 $2$ 秒至下一周期 $t=8$ 开始通行，$t=9$ 离开

最早到达 $=0$ 秒，最晚离开 $=9$ 秒，总时间 $=9-0=9$ 秒，最后一秒 $=9$。

样例 2

输入：

2,3,[E,E,S],[1,3,4]

输出：

[5,6]

解释：

周期 $C = 5$ 秒。

• E/W 方向红灯条件：$t \bmod 5 < 2$，绿灯条件：$t \bmod 5 \geq 2$
• S/N 方向红灯条件：$t \bmod 5 \geq 2$，绿灯条件：$t \bmod 5 < 2$

所有车辆都在同个 $C$ 周期内：

• E1 车 $1$ 秒到达：$1 < 2$ 红灯，等 $1$ 秒至 $t=2$ 开始通行，$t=3$ 离开（通行需 $1$ 秒）
• E2 车 $3$ 秒到达：$3 \geq 2$ 为绿灯；E1 已在 $t=3$ 离开，无需等待，$t=3$ 开始，$t=4$ 离开
• S 车 $4$ 秒到达：$4 \geq 2$ 红灯，等 $1$ 秒至下一周期 $t=5$ 开始，$t=6$ 离开

最早到达 $=1$ 秒，最晚离开 $=6$ 秒，总时间 $=6-1=5$ 秒，最后一秒 $=6$。