4025. Minimize the Maximum Waiting Time at Synchronized Traffic Lights

Description

You are given an integer period and an integer array lights, where lights[i] is the duration, in seconds, of the green phase of the ith traffic light.

At time 0, every traffic light starts at the beginning of its green phase. Their cycles are synchronized: every traffic light starts a new cycle at the same time, and every cycle lasts exactly period seconds. Therefore, the red phase of the ith traffic light lasts for period - lights[i] seconds.

You are also given an integer array arrivalTime, where arrivalTime[j] is the arrival time, in seconds, of the jth car.

Each car must be assigned to exactly one traffic light. Multiple cars may be assigned to the same traffic light. Any number of cars may cross the same traffic light simultaneously while it is green. Cars do not block or delay one another.

For a car j assigned to the ith traffic light, let r = arrivalTime[j] % period. If r < lights[i], its waiting time is 0. Otherwise, its waiting time is period - r.

The penalty of an assignment is the maximum waiting time among all cars.

Return an integer denoting the minimum possible penalty.

Example 1:

Example 2:

Example 3:

Constraints:

• 2 <= period <= 109
• 1 <= lights.length <= 104
• 1 <= lights[i] <= period - 1
• 1 <= arrivalTime.length <= 105
• 1 <= arrivalTime[i] <= 109

Solutions

Solution 1: Greedy

Let \(\textit{mx} = \max(\textit{lights})\) be the longest green duration. For car \(j\), let \(r = \textit{arrivalTime}[j] \bmod \textit{period}\).

• If \(r < \textit{mx}\), we can assign the car to the light with the longest green phase, and the waiting time is \(0\).
• If \(r \ge \textit{mx}\), then \(r \ge \textit{lights}[i]\) for every light, so the waiting time is \(\textit{period} - r\) regardless of the assignment.

Therefore, the penalty is the maximum of \(\textit{period} - r\) over all cars with \(r \ge \textit{mx}\). If every car can pass during a green light, the answer is \(0\).

The time complexity is \(O(n + m)\), and the space complexity is \(O(1)\), where \(n\) and \(m\) are the lengths of \(\textit{lights}\) and \(\textit{arrivalTime}\), respectively.

1
2
3
4
5
6
7
8
9

class Solution:
    def minPenalty(self, period: int, lights: list[int], arrivalTime: list[int]) -> int:
        mx = max(lights)
        ans = 0
        for x in arrivalTime:
            r = x % period
            if r >= mx:
                ans = max(ans, period - r)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution {
    public int minPenalty(int period, int[] lights, int[] arrivalTime) {
        int mx = 0;
        for (int x : lights) {
            mx = Math.max(mx, x);
        }

        int ans = 0;

        for (int x : arrivalTime) {
            int r = x % period;

            if (r >= mx) {
                ans = Math.max(ans, period - r);
            }
        }

        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution {
public:
    int minPenalty(int period, vector<int>& lights, vector<int>& arrivalTime) {
        int mx = ranges::max(lights);

        int ans = 0;

        for (int x : arrivalTime) {
            int r = x % period;

            if (r >= mx) {
                ans = max(ans, period - r);
            }
        }

        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func minPenalty(period int, lights []int, arrivalTime []int) int {
    mx := slices.Max(lights)
    ans := 0

    for _, x := range arrivalTime {
        r := x % period

        if r >= mx {
            ans = max(ans, period-r)
        }
    }

    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

function minPenalty(period: number, lights: number[], arrivalTime: number[]): number {
    const mx = Math.max(...lights);

    let ans = 0;

    for (const x of arrivalTime) {
        const r = x % period;

        if (r >= mx) {
            ans = Math.max(ans, period - r);
        }
    }

    return ans;
}

Comments