Задать вопрос
@Acvik2402
java

В чем ошибка в алгоритме поиска количества интервалов?

Товарищи знатоки, ткните пожалуйста в ошибку алгоритма:

Условие:

Считаем, что:

- начальное и конечное время всегда присутствуют;
- начальное время всегда меньше или равно конечному;
- начальное и конечное время включены в интервал.

Входные данные
Входная информация поступает из стандартного ввода, в первой строке приходит 1 число - количество вакансий. Каждая из следующих строк содержит информацию о вакансии в виде двух чисел – начальное и конечное время, они разделены пробелом. Время задается в секундах (https://ru.wikipedia.org/wiki/Unix-время). Некорректные данные на вход не поступают, дополнительные проверки не требуются.

Выходные данные
В качестве ответа в стандартный вывод через пробел нужно вывести два числа: количество найденных интервалов и сумму длительности интервалов в секундах (начальная и конечная секунды должны быть включены в интервал).

Пример 1
Входные данные:

1
1595862781 1595862785
Выходные данные: 1 5

Пример 2
Входные данные:

2
1595862781 1595862783
1595862782 1595862784
Выходные данные: 1 2

Пример 3
Входные данные:

2
1595862781 1595862782
1595862783 1595862784
Выходные данные: 2 4

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Main {

    public static void main(String[] args) throws IOException {
        // write your code here
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            String str = "";
            int count = 0;
            ArrayList<MyClass> arrayList = new ArrayList<>();
            if ((str = reader.readLine()) != null) {
                count = Integer.parseInt(str.trim());
            }

            for (int i = 0; i < count; i++) {
                str = reader.readLine();
                arrayList.add(new MyClass(Long.parseLong(str.split(" ")[0]), 1)); //начало
                arrayList.add(new MyClass(Long.parseLong(str.split(" ")[1])+1, -1));  //конец
            }
            if (count != 0) {
                findPair(arrayList);

            } else {
                System.out.println(0 + " " + 0);
            }
        }
    }

    private static void findPair(ArrayList<MyClass> arrayList) {
        Collections.sort(arrayList, Comparator.comparingLong(MyClass::getX));

        int maxVac = 0;
        int maxVacNum = 0;
        int resNum = 0;
        long resTime = 0;
        long maxVacTime = 0;
        long maxStart = 0;
        int cnt = 0;
        for (int j =0; j<arrayList.size(); j++) {
            if (arrayList.get(j).getY() > 0) {
                cnt +=arrayList.get(j).getY();
                if (cnt > maxVac) {
                    maxVac = cnt;
                    maxVacNum = 1;
                    maxStart = arrayList.get(j).getX();
                    maxVacTime = 0;
                } else if (cnt == maxVac) {
                    maxVacNum += 1;
                    maxStart = (arrayList.get(j).getX());

                }
            } else {
                if (cnt == maxVac) {
                    maxVacTime += (arrayList.get(j).getX() - maxStart);
                }
                cnt +=arrayList.get(j).getY();


            }
            if (maxVacNum >= resNum && maxVacTime > resTime) {
                resNum = maxVacNum;
                resTime = maxVacTime;
            }
        }
        System.out.println(resNum + " " + resTime);


    }

    public static class MyClass {
        long x;
        int y;

        public MyClass(long x, int y) {
            this.x = x;
            this.y = y;
        }

        public long getX() {
            return x;
        }

        public int getY() {
            return y;
        }

    }
}


тесты проходит, вроде все считает ровно, но валидатор умнее моих тестов
  • Вопрос задан
  • 392 просмотра
4 комментария
Подписаться 1 Средний 4 комментария
Решения вопроса 1
wataru
@wataru Куратор тега Алгоритмы
Разработчик на С++, экс-олимпиадник.
Вы правильно решили отсортировать концы отрезков, но эвристика с +-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.
Ответ написан
26 комментариев
26 комментариев
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы
Вакансии с Хабр Карьеры
Java-разработчик
ИТ-Холдинг Т1 • Москва
от 250 000 ₽
Java-разработчик в Маркет
Яндекс • Москва
от 180 000 до 350 000 ₽
Разработчик Java
Bell Integrator • Москва
от 230 000 ₽
Ещё вакансии
Заказы с Хабр Фриланса
Сделать простейшего голосового ассистента на c++ и winform
18 дек. 2024, в 23:08
1000 руб./за проект
Доработать функционал сайта
18 дек. 2024, в 20:59
3000 руб./за проект
Веб сервис для печатной мастерской (php+laravel+mysql)
18 дек. 2024, в 19:48
100000 руб./за проект
Ещё заказы