Помогите составить алгоритм. Есть ось координат. На ней лежат отрезки, которые могут пересекаться. Например 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();
}
}
Данная задача решается методом сканирующей прямой.
Разделим наши отрезки на некоторые события начала и конца, отсортируем их.
Будем идти по ним слева направо поддерживая некоторый баланс открывающих событий.
Тогда верно, что на какой-то координате отрезок точно открыт, если баланс во время её прохода положителен. Значит нужно разбирать два момента:
1) открывающее событие, когда баланс открытых был равен нулю. Это значит, что баланс станет единицей, то есть откроется хоть какой-то отрезок. Запомним координату в переменную start.
2) Закрывающее событие, после которого баланс станет равен нулю. Во время такого события необходимо добавить в некоторую переменную ответа ans разницу между текущей координатой и start.
Время, за которое алгоритм работает: O(nlogn), где n - количество исходных отрезков, время тратится на сортировку.
Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
Осваиваю Android studio java - хочу написать андроид приложение
Нужно создать свой пул соединений для Spring jdbcTemplate, поддерживающий lazy concurrent loading, и который будет создаваться как Spring BeanЯ так понимаю, что это...
Всем привет я написал чат, где мне сказали чтобы я сделал таймер который будет каждую секунду вызывать функцию (api/unread) из RestServiceЯ ранее создал...
Мучаюсь уже не один деньГде-то лежит небольшая маленькая ошибка и из-за неё вот ничего не получаеться