0

Написал прямо-таки алгоритм в лоб (я в курсе, что это решение очень далеко от оптимального, но я хочу разобраться в чём конкретно проблема данной реализации), на одном из тестов учебной платформы мой алгоритм отрабатывает неверно) Входные данные на котором проверяют мою реализацию мне к сожалению не показываются. Если кто-то видел эту задачу на LeetCode был бы признателен за ссылку. Ну либо помогите мне найти причину почему отрабатывает неверно) Ответ с учебной платформы: Failed test #4 of 15. got: 27 expected: 26 Прикрепляю условие задачивведите сюда описание изображения

n = int(input())

lines = []
lines.append([int(i) for i in input().split()])
minimum, maximum = lines[0][0], lines[0][1]
for _ in range(n - 1):
    start, end = map(int, input().split())
    lines.append([start, end])
    minimum = min(minimum, start)
    maximum = max(maximum, end)

result_list = []

while True:
    max_count_point = None
    max_count_list = []
    max_count = 0
    for point in range(minimum, maximum):
        current_count_list = []
        current_count = 0
        for line in lines:
            if line[0] <= point <= line[1]:
                current_count_list.append(line)
                current_count += 1
        if current_count > max_count:
            max_count_list = current_count_list
            max_count_point = point
            max_count = current_count
    if max_count == 0:
        break
    else:
        result_list.append(max_count_point)

    for line in max_count_list:
        lines.remove(line)

print(len(result_list))
print(*result_list)

1 ответ 1

0

Создаём список из пар всех концов отрезков вместе, содержащих координату и признак +1/-1 для начала/конца отрезка соответственно, сортируем по координате.

Обходим список по порядку. Если очередная пара содержит +1, добавляем +1 к количеству активных отрезков. Если содержит -1, и количество активных отрезков ненулевое, то выводим данную координату в результат и обнуляем количество активных отрезков.

(можно просто boolean наличие активных отрезков использовать вместо счётчика)

2
  • Да уже разобрался, спасибо) Стоило только не так прямолинейно переписать реализацию, как всё заработало
    – Mikhail
    14 июн 2021 в 7:14
  • @Mikhail Ваш алгоритм квадратичный или даже хуже. Для 100 точек это не проблема, а вот для 100000 или 1000000 нужно побыстрее. Приведённый подход обеспечивает время O(nlogn) (обусловлено сортировкой) и вообще будет полезен для других задач, связанных с набором перекрывающихся интервалов
    – MBo
    16 июн 2021 в 3:10

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.