2

Помогите составить алгоритм. Есть ось координат. На ней лежат отрезки, которые могут пересекаться. Например x1 x2 (0 5, 10 20, 15 30). Нужен алгоритм который найдет сумму длин отрезков без учета пересечений. То есть если брать координаты выше то длина должна быть 25. Я написал алгоритм, но работает не совсем правильно. Если есть несколько пересечений то длина вычисляется неправильно. Помогите исправить

public class Task5 {
public static void main(String[] args) {
    Scanner in = new Scanner(System.in);
    PrintWriter out = new PrintWriter(System.out);

    int n = in.nextInt();
    ArrayList<Pair<Integer, Integer>> pairs = new ArrayList<>();
    int length = 0;

    for (int i = 0; i < n; i++) {
        Pair<Integer, Integer> pair = new Pair(in.nextInt(), in.nextInt());
        pairs.add(pair);
    }

    for (int i = 0; i < n; i ++) {
        length += pairs.get(i).getValue() - pairs.get(i).getKey();
    }

    for (int i = 0; i < n - 1; i ++) {
        int x1 = pairs.get(i).getKey();
        int x2 = pairs.get(i).getValue();
        for (int j = i + 1; j < n; j++) {
            int y1 = pairs.get(j).getKey();
            int y2 = pairs.get(j).getValue();

            if (x1 == y1 && x2 == y2) length = length - (y1 - y2);
            else if (x1 < y1 && x2 > y2) length = length - (y2 - y1);
            else if (x1 > y1 && x2 < y2) length = length - (x2 - x1);
            else if (x1 < y1 && x2 < y2) length = length - (x2 - y1);
            else if (x1 > y1 && x2 > y2) length = length - (y2 - x1);

        }
    }

    out.println(length);
    out.flush();
}

}

2
  • 1
    Сперва отсортируйте по возрастанию начал, а потом сливайте в один проход.
    – Akina
    9 янв 2020 в 17:02
  • Спаисбо помогли 9 янв 2020 в 17:05

1 ответ 1

2

Данная задача решается методом сканирующей прямой.

Разделим наши отрезки на некоторые события начала и конца, отсортируем их.

Будем идти по ним слева направо поддерживая некоторый баланс открывающих событий.

Тогда верно, что на какой-то координате отрезок точно открыт, если баланс во время её прохода положителен. Значит нужно разбирать два момента:

1) открывающее событие, когда баланс открытых был равен нулю. Это значит, что баланс станет единицей, то есть откроется хоть какой-то отрезок. Запомним координату в переменную start.

2) Закрывающее событие, после которого баланс станет равен нулю. Во время такого события необходимо добавить в некоторую переменную ответа ans разницу между текущей координатой и start.

Время, за которое алгоритм работает: O(nlogn), где n - количество исходных отрезков, время тратится на сортировку.

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.