Завершение бинарного поиска еще одной задачей: прибивание досок.
Привет! Далее следует больше бинарного поиска. Пришло время завершить еще одним классным испытанием: прибиванием досок. Общие основы этого алгоритма бинарного поиска описаны в предыдущей статье, которую я написал на эту тему, поэтому, если вы чувствуете, что вам нужно освежить свои знания в области бинарного поиска, не стесняйтесь делать это.
Мы снова пачкаем руки, потому что пришло время прибить несколько досок! :)
Задача: нам даны два непустых массива A и B, состоящих из N целых чисел. Эти массивы представляют собой N досок. A[i] — начало и B[i] — конец i-й доски; нам также дан третий непустой массив C, состоящий из M целых чисел. Этот массив представляет M гвоздей: C[i] — позиция, в которую мы можем забить i-й гвоздь.
Доска, определяемая A[i] и B[i], считается прибитой, если существует гвоздь C[j] такой, что A[i] ≤ C[j] ≤ B[i].
Суть в том, чтобы найти минимальное количество гвоздей, которое необходимо использовать, пока все доски не будут прибиты. Другими словами, задача указывает, что мы должны найти такое значение k, при котором все доски будут прибиты после использования только первых k гвоздей. Для каждой доски, заданной A[i] и B[i], такой, что 0 ≤ i ‹ N, должен существовать гвоздь C[j] такой, что j ‹ k и A[i] ≤ C[j] ≤ B[ я].
Также в задаче указано, что если мы не можем прибить все доски, мы должны вернуть -1.
Чтобы лучше понять проблему, Codility приводит пример. Рассмотрим следующие заданные массивы:
- A=[1, 4, 5, 8]
- B=[4, 5, 9, 10]
- C=[4, 6, 7, 10, 2]
Мы можем определить четыре доски как [1, 4], [4, 5], [5, 9] и [8, 10].
Если мы используем следующие гвозди:
- 0, то [1, 4] и [4, 5] будут прибиты (C[0]=4)
- 0, 1, то [1, 4], [4, 5] и [5, 9] будут прибиты (C[0]=4, C[1]=6])
- 0, 1, 2, то [1, 4], [4, 5] и [5, 9] будут прибиты (по тем же причинам)
- 0, 1, 2, 3, тогда все доски будут прибиты.
Таким образом, 4 — это наше минимальное количество гвоздей, которые при последовательном использовании позволяют прибить все доски.
Условия и ограничения: N и M — целые числа в диапазоне [1…30 000]. Каждый элемент массивов A, B и C является целым числом в диапазоне [1…2*M]. Кроме того, A[i] ≤ B[i] (начальное положение доски всегда будет не больше, чем конечное положение).
Вот подход, который я использовал. Тот, который дал мне оценку 100 % и сложность O((N + M) * log(M)):
- инициализируйте результат равным -1, на случай, если мы не сможем прибить все доски; также инициализируйте интервал поиска для бинарного поиска: верхний предел = количество гвоздей, нижний предел = 0;
- выполнить бинарный поиск по индексу гвоздей. Нам нужно найти тот минимальный показатель, ниже которого предыдущие гвозди успевают прибить все доски;
- используйте карту гвоздей для вычисления суммы префиксов, чтобы ускорить функцию, которая проверяет, прибита ли доска или нет. Доска считается прибитой, если между ее концом и точкой начала (включительно) имеется хотя бы один гвоздь. Если в какой-то доске 0 гвоздей, это сигнализирует о том, что мы должны увеличить кандидата (середину), потому что, если хотя бы одна доска осталась без гвоздей, это означает, что мы не набрали достаточное количество гвоздей для всех досок, поэтому необходимо увеличить количество гвоздей-кандидатов;
- если все доски можно прибить гвоздями чуть ниже среднего кандидата, то обновить переменную результата;
- повторять цикл до тех пор, пока верхний предел не упадет ниже нижнего предела интервала поиска;
- в итоге наша результирующая переменная будет либо равна -1, либо будет изменена, если такой минимальный индекс был найден. Мы вернем этот результат.
def check_nailed(start_pts, end_pts, nails, candidate):
"""Check if candidate nails are nailing all planks."""
# build and populate prefix sums nail map
nail_map = [0] * (2 * (len(start_pts) + 1) + 1)
for nail in nails[0:candidate]:
nail_map[nail] = 1
for i in range(1, len(nail_map)):
nail_map[i] += nail_map[i - 1]
# if there's at least one not-nailed plank, return false
for i, _ in enumerate(start_pts):
# plank not nailed = no nail between end and start point
if nail_map[end_pts[i]] == nail_map[start_pts[i] - 1]:
return False
# all planks nailed using candidate number of nails
return True
def solution(start_pts, end_pts, nails):
"""Solution method implementation."""
# initialize binary search and result vars
upper, lower, result = len(nails), 0, -1
# apply binary search algorithm
while upper >= lower:
# get middle point
mid = (upper + lower) // 2
# determine if all planks are nailed using "mid" nails
all_nailed = check_nailed(start_pts, end_pts, nails, mid)
# not all planks nailed. Readjust binary search interval
if not all_nailed:
lower = mid + 1
# all planks nailed. Update result
else:
result = mid
upper = mid - 1
return result
Довольно просто, как только мы получим четкое представление о том, чего нам нужно достичь и, самое главное, как этого достичь.
Теперь вы могли заметить, что когда мы обновляем результирующую переменную, это просто простое безусловное присваивание, но вы, вероятно, ожидали увидеть что-то вроде
if mid < result:
result = mid
или что-то более компактное, например:
result = min(result, mid)
а не просто result = mid. Алгоритм бинарного поиска, как я представил его выше, гарантирует, что при нахождении результата (результат = средний) мы изменим окно поиска с [нижний…верхний] на [нижний…средний-1], поэтому мы можем рассчитывать на тот факт, что следующий конечный результат будет даже ниже, чем предыдущий mid, что позволит нам получить минимальное количество гвоздей, необходимое для прибивания всех досок.
Бинарный поиск в настоящее время является обязательным элементом вашей базы знаний, что, учитывая все концепции оптимизации процессов, о которых мы все постоянно слышим по всему миру, поскольку это очень эффективный алгоритм поиска. Сделайте это, и вы обязательно поблагодарите себя позже за то, что сделали это.
До скорого! Удачного кодирования!
Больше контента на plainenglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку здесь.
