Traffic Lights

There is a street of length x whose positions are numbered 0,1,...,x. Initially, there are no traffic lights, but n sets of traffic lights are added to the street one after another.

Your task is to calculate the length of the longest passage without traffic lights after each addition.

Example:

Input: k = 8, n = 3, arr = {3, 6, 2}
Output: 5 3 3

Approach

C++

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

void trafficLights(int k, int n, vector<int> &arr)
{

    multiset<int> ms;
    set<int> st;
    st.insert(0);
    st.insert(k);
    ms.insert(k);
    for (int i = 0; i < n; i++)
    {
        int x = arr[i];
        auto r = st.upper_bound(x);
        auto l = prev(r);
        ms.erase(ms.find(*r - *l));
        ms.insert(*r - x);
        ms.insert(x - *l);
        st.insert(x);
        cout << *ms.rbegin() << " ";
    }
}

int main()
{
    int k = 8, n = 3;
    vector<int> arr = {3, 6, 2};

    trafficLights(k, n, arr);

    return 0;
}