Прикосновение сегментов

Question

Может ли кто-нибудь предложить мне алгоритм для этого.

Вам даются начальные и конечные точки N сегментов по оси x. Сколько из этих сегментов можно затронуть даже на их краях ровно двумя перпендикулярными им линиями?

Пример ввода:

3 
5 
2 3 
1 3 
1 5 
3 4 
4 5 
5 
1 2 
1 3 
2 3 
1 4 
1 5 
3 
1 2 
3 4 
5 6 

Пример вывода:

Case 1: 5 
Case 2: 5 
Case 3: 2 

Объяснение:

• Случай 1: Мы рисуем две линии (параллельные оси ординат) пересечение Х- оси в точках 2 и 4. Эти две линии коснутся всех пяти сегментов.
• Корпус 2: Мы можем касаться всех точек даже с одной осью пересечения X-оси на 2.
• Случай 3: В этом случае невозможно коснуться более двух точек.

Ограничения:

1 ≤ N ≤ 10^5 
0 ≤ a < b ≤ 10^9 

Answer 1

Пусть Предположим, что у нас есть структура данных, которая эффективно поддерживает следующие операции:

1. Добавить сегмент.

2. Удалить сегмент.

3. Возврат максимального количества сегментов, которые покрывают одну точку (то есть «лучшую» точку).

Если есть такая структура, мы можем получить эффективно использовать исходную задачу следующим образом:

1. Давайте создадим массив событий (одно событие для начала каждого сегмента и один для конца) и сортировать по координате x.

2. Добавить все сегменты в магическую структуру данных.

3. Итерируйте по всем событиям и выполните следующие действия: при начале сегмента добавьте его к числу сегментов, охватываемых в данный момент, и удалите их из этой структуры данных. Когда сегмент заканчивается, вычтите его из числа текущего охваченного сегмента и добавьте этот сегмент в магическую структуру данных. После каждого события обновите ответ на значение количества сегментов, охваченных в данный момент (он показывает, сколько сегментов покрывается точкой, которая соответствует текущему событию) плюс максимум, возвращаемый структурой данных, описанной выше (это показывает, как мы может выбрать другой пункт наилучшим образом).

Если эта структура данных могут выполнять все указанные операции в O(log n), то есть O(n log n) решения (мы сортируем событие и сделать один проход над отсортированным массивом делает постоянное число запросов к этой структуре данных для каждого мероприятие).

Итак, как мы можем реализовать эту структуру данных? Ну, здесь отлично работает сегментное дерево. Добавление сегмента добавляет один к определенному диапазону. Удаление сегмента вычитает один из всех элементов в определенном диапазоне. Получить ting максимум - это стандартная максимальная операция на дереве сегментов. Поэтому нам нужно дерево сегментов, которое поддерживает две операции: добавьте константу в диапазон и получите максимум для всего дерева. Это можно сделать в O(log n) времени на запрос.

Еще одно примечание: стандартное дерево сегментов требует, чтобы координаты были маленькими. Мы можем предположить, что они никогда не превышают 2 * n (если это не так, мы можем их сжать).

Answer 2

Решение O(N*max(logN, M)), где M - средний размер сегмента, реализованный в Common Lisp: touching-segments.lisp.

Идея состоит в том, чтобы сначала вычислить слева направо в каждой интересной точке число сегментов, которые будут затронуты линией там (open-left-to-right на код lisp). Стоимость: O (NlogN)

Затем справа налево он вычисляет, снова на каждом интересном месте P, лучшее место для линии с учетом сегментов полностью вправо из P (open-right-to-left на LISP кода). Стоимость O (N * max (logN, M))

Тогда это просто вопрос поиска точки, в которой сумма обоих значений вершин. Стоимость O (N).

Код едва проверен и может содержать ошибки. Кроме того, я не потрудился обрабатывать граничные случаи, когда число сегментов равно нулю.

Answer 3

1. Проблема может быть решена в O (Nlog (N)) раз в тесте.

2. Заметим, что существует оптимальное размещение двух вертикальных линий, каждая из которых проходят через некоторый отрезок конечных точек

3. координаты сегментов компресса. Дополнительная информация: Что такое coordinate compression?

4. Построить отсортированный набор конечных точек сегмента X

5. сортировки сегменты [a_i, b_i] от a_i

6. Пусть й очереди приоритетов, который хранит правильные концы сегментов обработано до сих пор

7. Пусть T - дерево с максимальным интервалом, построенное по координатам x. Некоторые полезные считывании на What are some sources (books, etc.) from where I can learn about Interval, Segment, Range trees?

8. Для каждого сегмента сделать [a_i, b_i] -range приращения на 1 запрос к Т. Это позволяет найти максимальное число сегментов, охватывающих некоторые х в [а, Ь]

9. итерацию по элементам х из X. Для каждого х сегментов процесса (не уже обработанные) с х> = a_i. Обработка включает в себя толкание b_i до Q и создание [a_i, b_i] -разрядное увеличение на - (- 1) запрос к T. После удаления из Q всех элементов < x, A = Q.size равно числу сегментов, покрывающих x. B = T.rmq (x + 1, M) возвращает максимальное количество сегментов, которые не покрывают x, и покрывают некоторое фиксированное y> x. A + B является кандидатом на ответ.

Источник: http://www.quora.com/What-are-the-intended-solutions-for-the-Touching-segments-and-the-Smallest-String-and-Regex-problems-from-the-Cisco-Software-Challenge-held-on-Hackerrank