Можно разбить задачи на куски по T штук. Каждый кусок хранить в векторе, отсортированном по времени.
Тогда итерироваться придется по вектору, то есть с низкой константой.
А вставка будет не очень дорогой
Имеешь в виду, создать вектор в векторе? Например, у нас есть вектор A в котором хранится вектор B, а вектор B хранит список задач. Теперь,, каждый раз когда мы добавляем задачу, мы должны итерироваться по вектору A, получая каждый элемент (тобиь, вектор B), а из вектора B мы вытаскиваем первый и последний элемент и сравниваем время