Покрытие отрезков точками
Эта проблема была взята из Coursera Специализация по структурам данных и алгоритмам, в частности из Курса Algorithmic Toolbox, неделя 3: Жадные алгоритмы, которые я недавно завершил. Если вы проходите этот курс или планируете пройти этот курс, пожалуйста, не ждите решения, поскольку оно противоречит Кодексу чести и не принесет вам никакой пользы.
Введение в проблему
Вам дается набор сегментов на линии, и ваша цель - отметить как можно меньше точек на линии, чтобы каждый сегмент содержал хотя бы одну отмеченную точку.
описание проблемы
Задача. Для набора n сегментов {[a (0), b (0)], [a (1), b (1)],…, [ a (n) −1, b (n) −1]} с целыми координатами на прямой, найдите минимальное количество m точек, при котором каждый сегмент содержит хотя бы одну точку. То есть найти набор целых чисел X минимального размера, такой, что для любого отрезка [a (i), b (i)] существует точка x ∈ X такое, что a (i) ≤ x ≤ b (i).
Формат ввода. Первая строка ввода содержит число n сегментов. Каждая из следующих n строк содержит два целых числа a (i) и b (i) (разделенных пробелом), определяющих координаты конечных точек. i-го сегмента.
Ограничения. 1 ≤ n ≤ 100; 0 ≤ a (i) ≤ b (i) ≤ 10 ^ 9 для всех 0 ≤ i ‹n.
Формат вывода. Выведите минимальное количество m точек в первой строке и целые координаты m точек (разделенных символом пробелы) во второй строке. Вы можете выводить точки в любом порядке. Если таких наборов точек много, вы можете вывести любой набор. (Нетрудно увидеть, что всегда существует набор точек минимального размера, при котором все координаты точек являются целыми числами.)
Ограничения по времени. C: 1 секунда, C ++: 1 сек, Java: 1,5 сек, Python: 5 сек. C #: 1,5 секунды, Haskell: 2 секунды, JavaScript: 3 секунды, Ruby: 3 секунды, Scala: 3 секунды
Ограничение памяти. 512 Мб
Образец 1
Ввод:
3
1 3
2 5
3 6
Выход:
1
3
Пояснение:
В этом примере у нас есть три сегмента: [1,3], [2,5], [3,6] (из длина 2,3,3 соответственно). Все они содержат точку с координатой 3: 1 ≤ 3 ≤ 3, 2 ≤ 3 ≤ 5, 3 ≤ 3 ≤ 6.
Образец 2
Ввод:
4
4 7
1 3
2 5
5 6
Выход:
2
3 6
Пояснение:
Второй и третий сегменты содержат точку с координатой 3, а первый и четвертый сегменты содержат точка с координатой 6. Все четыре сегмента не могут быть покрыты одной точкой, поскольку сегменты [1,3] и [5,6] не пересекаются.
Что делать
Чтобы разработать жадный алгоритм для этой проблемы, рассмотрите сегмент с минимальной правой конечной точкой. Как безопасный способ прикрыть его точкой?
Мое решение:
Намекать:
Ключ в том, чтобы отсортировать сегменты по их конечным точкам.
Если вы можете придумать какой-либо другой способ улучшить этот алгоритм или указать на что-то, что, по вашему мнению, я сделал неправильно, вы более чем рады связаться со мной, ответив к этому и указав на ошибки. Если вам нравится это решение, нажмите кнопку «Рекомендовать» ниже, это будет много значить для меня. Спасибо.
