Encontrei uma boa solução para esse problema nessa pargunta aquiHow to find all K-th elements for each expiration time, o melhor tempo obtido foi utilizando Arrays ao invés de List/Streams. Caso o problema te forneça os dados em List é só fazer um parse para Array e no final realiza outro parse de volta para List, só dessa forma consegui passar em todos os caso de teste.
public static int[] kth(int k, int[] t, int[] e) {
int[] kth = new int[e.length];
if (k > t.length)
return kth;
Arrays.sort(e);
int c = 0;
for (int i = 0; i < e.length; i++) {
for (int j = 0; j < t.length; j++) {
if (t[j] >= e[i])
c++;
if (c >= k) {
kth[i] = j + 1;
break;
}
}
if (c < k)
break;
c = 0;
}
return kth;
}