Hi, I am working on this problem https://cses.fi/problemset/task/1163/. My idea is basically to process the traffic lights in reverse order. First, I will find the max gap when all traffic lights are placed. Then, one by one in reverse order (of the input), I will use the ceiling/floor function of the TreeSet to see the size of the new gap that has opened up after I remove this current traffic light. Then, I compare it with the previous max answer, and I will only keep the max.
However, I am getting TLE on the last 7 cases, AC the first 5. I don’t know if it is because Java is too slow for this problem, because that has happened to me before.
import java.io.*;
import java.util.*;
class cses {
static int n;
static int m;
public static void main(String[] args) throws IOException{
BufferedReader file = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(file.readLine());
int x = Integer.parseInt(st.nextToken());
n = Integer.parseInt(st.nextToken());
TreeSet<Integer> set = new TreeSet<>();
set.add(0);
set.add(x);
int[] arr = new int[n];
st = new StringTokenizer(file.readLine());
for (int i=0; i<n; i++){
arr[i] = Integer.parseInt(st.nextToken());
set.add(arr[i]);
}
int ans = 0;
int prev = 0;
for (int curr : set){
ans = Math.max(ans, curr-prev);
prev = curr;
}
int[] out = new int[n];
out[n-1] = ans;
for (int i=n-1; i>0; i--){
int curr = arr[i];
set.remove(curr);
ans = Math.max(set.ceiling(curr)-set.floor(curr), ans);
out[i-1] = ans;
}
for (int i : out){
System.out.print(i + " ");
}
}
}