Задача на отрезки на числовой прямой

Записался на курс алгоритмы и структуры данных. Не могу никак решить задачу: На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка (Li и Ri). Найти сумму длин частей числовой прямой, окрашенных ровно в один слой. Используемый язык java, другие также принимаются
input
3
1 4 7 8 2 5
output 3 input
9
2 9 0 1 7 12 5 12 9 13 9 14 10 18 17 18 2 10
output 4
UPD Что я пытался делать 1) сортировать все точки и держать к какому концу отрезка она находиться на 1 первый тест легко пишутся условия когда нужно посчитать сумму ко 2му не подходит
int sum = 0; if(mass.length==1) sum+=mass[1].dot-mass[0].dot; else { sum+= mass[1].dot-mass[0].dot; for (int i = 2; i < n * 2; i++) { if(mass[i].l==false){ // если это не левый конец if (mass[i-1].l==false) sum+=mass[i].dot-mass[i-1].dot; if(mass[i-1].l==true&&mass[i-2].l==false) sum+=mass[i].dot-mass[i-1].dot; }else {
if(mass[i-1].l==true) sum+= mass[i].dot-mass[i-1].dot;
}
2) Сортировать все отрезки в виде классов (point( 1 4) point (2 5) point (7 8)) также с ифами все возможные варианты не получилось покрыть, Есть какие-то еще идеи или только в этих 2-х направлениях нужно искать подходящие условия срабатывания счетчика
UPD
Вот похожая задача на нахождение длины объединения отрезков на прямой. ток не совсем понимаю синтаксис и как перевести на java
unsigned segments_union_measure (const vector > & a) { unsigned n = a.size(); vector > x (n*2); for (unsigned i=0; i sort (x.begin(), x.end());
unsigned result = 0; unsigned c = 0; for (unsigned i=0; i

Ответ

Задачи на интервалы решаются сортировкой координат, и перебором подряд от меньших к большим, считая «текущее» кол-во активных.
Напр., даны отрезки [1,5], [2,3], [3,9]
Тут ещё важно, каковы крайние точки - для простоты считаем, что все края «включены».
Сортируем координаты, не забывая, где какая - одни из них точки входа (in), другие - выхода (out):
1 i 2 i 3 o 3 i 5 o 9 o
Изначально кол-во включённых слоёв 0. Когда "i" добавляем 1, когда "o" – вычитаем. Пошли:
- - 0 1 i 1 - начался нужный отрезок - в результат добавим [1, ? 2 i 2 - != 1, закончился – в результат добавили [1,2] 3 o 1 - снова начался нужный 3 i 2 - и тут же закончился, ничего не делаем 5 o 1 - начался нужный [5, ? 9 o 0 - закончился, в результат добавили [5,9]
Результат: [1,2], [5,9]. Складываем длины 1+4 = 5. Ответ: 5