1 Тема от aza_inf

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Тема: закраска прямой

Закраска прямой
(Время: 1 сек. Память: 16 Мб)
На числовой прямой окрасили N отрезков. Известны координаты левого и правого концов каждого отрезка (Li и Ri). Найти длину окрашенной части числовой прямой.

Входные данные

Входной файл INPUT.TXT в первой строке содержит число N, в следующих N строках - пары Li и Ri. Ограничения: все числа целые, не превышающие 109 по абсолютной величине, 1 <= N <= 15 000.

Выходные данные

В выходной файл OUTPUT.TXT выведите длину окрашенной части прямой.

Пример
input.txt
2
1 3
2 4
output.txt
3

кто может решить эту задачу разными способами? у кого есть идеи?

2 Ответ от brainail

  • brainail
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-22
  • Сообщений: 165

Re: закраска прямой

Эта стандартная задача, запишем начало отрезков как начало события а конец отрезков как конец события в один массив всё.
Отсортируем, далее как в скобочной последовательности, пока последовательность не закрыта прибавляем длины отрезков к ответу. Пишется это пару минут.

Сложность O(NlogN).

3 Ответ от aza_inf

  • aza_inf
  • Участник
  • Неактивен
  • Зарегистрирован: 2009-06-30
  • Сообщений: 78

Re: закраска прямой

не, я это знаю, но кто может придумать решение с использованием дерева отрезков?
и еще, кто может дать ссылки на задачи на дерево отрезков?

4 Ответ от coder.ua

  • coder.ua
  • Участник
  • Неактивен
  • Зарегистрирован: 2010-03-06
  • Сообщений: 78

Re: закраска прямой

Вот ссылка на раздел где есть теория и сами задачи на структуры данных и на дерево отрезков в том числе- http://informatics.mccme.ru/moodle/cour … .php?id=18