I have same doubt pls help

Approach explanation:

Each light follows this pattern after installation at time a[i]:

• ON during [a[i], a[i] + k - 1]
• OFF during [a[i] + k, a[i] + 2k - 1]
• Then the same pattern repeats every 2k minutes.

So the ON intervals for room i are:

[a[i] + 2k·j, a[i] + 2k·j + k - 1]

First, sort the installation times. Let the latest installation time be:

a[n - 1]

The latest-installed light is initially ON only in:

[a[n - 1], a[n - 1] + k - 1]

Therefore, the earliest answer, if it exists, must be inside this interval. We store its right endpoint:

ll mx = a[n - 1] + k - 1;

For every other room, we move the beginning of its ON interval forward by multiples of 2k:

a[i] += ((mx - a[i]) / (2 * k)) * 2 * k;

Adding 2k does not change the light's state pattern. This finds the latest ON-interval starting time of that room which is not greater than mx.

After adjusting all rooms, sort again. Let:

candidate = a[n - 1];

This is the latest starting point among the selected ON intervals. It is the earliest possible time when all those intervals could overlap.

For every room, its selected ON interval ends just before:

a[i] + k

Therefore, if:

a[i] + k <= candidate

then that room has already turned OFF at candidate, so there is no common ON time and the answer is -1.

Otherwise, candidate belongs to every selected ON interval, so all lights are ON at that moment, and it is the earliest possible answer.

sort(a.begin(), a.end());

ll mx = a[n - 1] + k - 1;

// Move every earlier room to its latest relevant ON interval.
for (int i = 0; i < n - 1; i++) {
    a[i] += ((mx - a[i]) / (2 * k)) * 2 * k;
}

sort(a.begin(), a.end());

ll candidate = a[n - 1];

for (int i = 0; i < n - 1; i++) {
    if (a[i] + k <= candidate) {
        cout << -1 << '\n';
        return;
    }
}

cout << candidate << '\n';

Time complexity: O(n log n) because of sorting. Space complexity: O(n) for storing the array.

See code for more clarification

Maybe read the editorial