CSES - Traffic Lights

In this problem, we are given an empty interval of length $x$ spanning from 0 to $x$, and $n$ points are added to the interval chronologically. We want to find the largest gap between the points after each step.

Unofficial Editorial (C++)

Solution 1

Let's create a set and a multiset. The set will store the positions of the traffic lights, while the multiset will keep track of the "gaps" between the lights. The multiset keeps expanding because more lights are added, and you just need to print the length of the longest passage without traffic lights after each addition (i.e. the max element of that multiset). This element is the last element by default.

Note that when placing a new traffic light on the road, that light will split the gap between two adjacent lights into two smaller pieces, so you also have to remove the length of that gap in the multiset and add two new lengths to the multiset.

Copy
#include <bits/stdc++.h>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int street_len;
	int light_num;
	cin >> street_len >> light_num;

Solution 2 - Going Backwards

We'll start by trying to find the maximum gap once all the traffic lights are added. This is the last number we'll output, so we'll add it to the end of our output array. Then, we'll remove traffic lights in the reverse order to how they were added, and find the gap each removal creates.

This gap is just the distance between the two street coordinates (either a traffic light or the beginning or ending of the street) next to a given traffic light stored in our set, so we can use our set to find these values and subtract them to get our gap.

But this gap may not be the maximum gap. We'll compare this to the gap we found once all the traffic lights are added, and set the max gap to the greater value. We'll then set the next lowest element in the output array to this value, which will represent the greatest gap prior to adding the traffic light we just removed.

Implementation 1

Time Complexity: $\mathcal{O}(n \log n)$

Copy
#include <algorithm>
#include <iostream>
#include <set>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {

Copy
import java.io.*;
import java.util.*;

public class TrafficLights {
	public static void main(String[] args) throws IOException {
		Kattio io = new Kattio();

		int streetLength = io.nextInt();
		int lightNum = io.nextInt();

Implementation 2

The above solution uses a sorted set. While this does make it easier to implement, it also adds an extra $\log n$ factor to the time complexity. To remove this, we can use a doubly linked list instead.

Copy
#include <algorithm>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {
	int street_len;