Найти общую длину отрезков

186
13 февраля 2022, 01:40

Помогите составить алгоритм. Есть ось координат. На ней лежат отрезки, которые могут пересекаться. Например 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();
}

}

Answer 1

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

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

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

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

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

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

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

READ ALSO
Как написать событие нажатия кнопки

Как написать событие нажатия кнопки

Осваиваю Android studio java - хочу написать андроид приложение

125
Пул соединений для Spring jdbcTemplate

Пул соединений для Spring jdbcTemplate

Нужно создать свой пул соединений для Spring jdbcTemplate, поддерживающий lazy concurrent loading, и который будет создаваться как Spring BeanЯ так понимаю, что это...

73
Как переделать scheduler для vaadin 14 (spring boot и vaadin 14)

Как переделать scheduler для vaadin 14 (spring boot и vaadin 14)

Всем привет я написал чат, где мне сказали чтобы я сделал таймер который будет каждую секунду вызывать функцию (api/unread) из RestServiceЯ ранее создал...

94
Could not find or load main class while opening .JAR using CMD | Gradle | Intellij-idea

Could not find or load main class while opening .JAR using CMD | Gradle | Intellij-idea

Мучаюсь уже не один деньГде-то лежит небольшая маленькая ошибка и из-за неё вот ничего не получаеться

96