Вы правильно решили отсортировать концы отрезков, но эвристика с +-1 в виде второго параметра сортировки у вас не работает. Похоже там и есть ошибка. Попробуйте тест, "6 100 102 100 102 100 102 102 104 102 104 102 104". Ответ должен быть - 1 отрезок длиной 1 (там 6 вакансий в 102-ой секунде). Другой интересный тест "6 100 102 100 102 100 102 103 104 103 104 103 104". Тут ответ 1 5 (3 вакансии).
Проблема в том что такой подход с сортировкой работает, если границы отрезка - точки на прямой. У вас же в задаче границы отрезка - это секунды.
Я бы прибавлял 1 к концам отрезков и считал границы точками на числовой прямой.
Далее, я бы разделил код выделения отрезков и поиска максимума.
У вас очень сложная логика и там может быть ошибка. Сложно за всем уследить.
По памяти у вас вроде бы проблем нет - ну заведите еще один массив, куда будете складывать {количество вакансий, длина отрезка}. Складывайте туда только отрезки с разным количеством вакансий. Потом (или во время складывания) найдите там макимальное количество вакансий. И последним проходом подсчитайте сумму и количество элементов в с заданным количеством вакансий.
Что-то вроде этого (код на недо-жаве, поправьте сами):
// class Segment: имеет length и count.
// result - arrayList of Segment
// arrayList содержит MyClass отсортированные по X границы отрезков (Y= +1 для начала и -1 для конца. Концы отрезков имеют сдвинутую на +1 X).
prev_x = arrayList[0].GetX();
cnt = 0;
for (MyClass mc : arrayList) {
cur_length = mc.GetX() - prev_x;
// рассматриваем отрезок (prev_x, mc.GetX()), не включая границы-точки!
// Поэтому GetY() прибавляем в конце!
// пропускаем отрезки нулевой длины - они из-за совпадающих точек и смысла не несут
if (cur_length > 0) {
// новый отрезок добавляем, только если разное количество вакансий.
if (result.size() == 0 || result[result.size() - 1].cnt != cnt) {
result.add(new Segment(cur_length, cnt);
} else {
result[result.size()-1].length += cur_length;
}
cnt += mc.GetY();
prev_x = mc.GetX();
}
max = 0;
for (Segment s : result) {
if (s.cnt > max) max = s.cnt;
}
length = 0;
total = 0;
for (Segment s : result) {
if (s.cnt == max) {
length += s.length;
total += 1;
}
}
// print total length.
