Найти алгоритм подсчета количеств множественного перекрытия интервалов, а также найти длительность таких интервалов

Question

Условия задачи:

Ограничение времени, с 2
Ограничение памяти, МБ 96
Общее число попыток отправки 15

Петя решил узнать, когда программисту выгоднее всего искать работу на hh.ru. Конечно, когда больше всего открыто вакансий.

Он выгрузил в текстовый файл время открытия и закрытия всех подходящих вакансий за 2019 год.

Теперь нужно определить период времени, когда открытых вакансий было больше всего.

Считаем, что:

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

Входные данные Входная информация поступает из стандартного ввода, в первой строке приходит 1 число - количество вакансий. Каждая из следующих строк содержит информацию о вакансии в виде двух чисел – начальное и конечное время, они разделены пробелом. Время задается в секундах (https://ru.wikipedia.org/wiki/Unix-время). Некорректные данные на вход не поступают, дополнительные проверки не требуются.

Выходные данные В качестве ответа в стандартный вывод через пробел нужно вывести два числа: количество найденных интервалов и сумму длительности интервалов в секундах (начальная и конечная секунды должны быть включены в интервал).

Пример 1
Входные данные:

1
1595862781 1595862785
Выходные данные: 1 5


Пример 2
Входные данные:

2
1595862781 1595862783
1595862782 1595862784
Выходные данные: 1 2


Пример 3
Входные данные:

2
1595862781 1595862782
1595862783 1595862784
Выходные данные: 2 4

Вот мой код. Тесты из примеров проходит но на закрытых данных где-то дает не правильный ответ.

def count_intervals(intervals):
    
    list_to_check = []
    for interval in intervals:
        list_to_check.append([interval[0],1])
        list_to_check.append([interval[1],-1])
    list_to_check.sort()
    
    count_interval = 0
    
    job_count = 0
    job_count_was = 0
    start_interval = False
    
    sum_duration = 0
    
    for i, interval in enumerate(list_to_check):
        
        job_count_was = job_count
        job_count += interval[1]
        
        if start_interval == True and job_count < job_count_was:
            sum_duration += interval[0] - list_to_check[i-1][0] + 1
            count_interval += 1
            start_interval = False
        elif job_count > job_count_was:
            start_interval = True
            
    return [count_interval , sum_duration]
    
      
input_intervals = int(input())
intervals = []
while input_intervals > 0:
    input_intervals -= 1
    interval_start, interval_end = input().split()
    interval_start = int(interval_start)
    interval_end = int(interval_end)
    intervals.append([interval_start, interval_end])


resault_intervals = count_intervals(intervals)

print(resault_intervals[0], resault_intervals[1])

Answer 1

Как-то запутано всё с образованием новых интервалов. С многократным перекрытием работает?

Есть такой алгоритм (со сложностью O(nlogn) за счёт сортировки):

Занести в список для всех начал и концов пары, состоящие из времени и поля признака -1 для конца, +1 для начала.

Отсортировать по времени

Пройти по списку, добавляя значение поля +-1 к счётчику активных интервалов.

Если счётчик уменьшается, сравнить его с максимумом, и при превышении заменить максимум и обновить суммарное время, при равенстве добавить последний промежуток (от момента роста счётчика) к суммарному времени

input_intervals = int(input())
points = []
while input_intervals > 0:
    input_intervals -= 1
    interval_start, interval_end = input().split()
    interval_start = int(interval_start)
    interval_end = int(interval_end)
    points.append([interval_start, -1])  # начало делаем -1 для нужной сортировки
    points.append([interval_end, 1])

points.sort()
#print(points)

maxvac = 0
maxvacnum = 0
maxvactime = 0
count = 0
for p in points:
    if p[1] < 0:  #начало
        count += 1
        if count > maxvac:   #всё обнуляем
            maxvac = count
            maxvacnum = 1
            maxstart = p[0]
            maxvactime = 0
        elif count == maxvac:
            maxvacnum += 1   #обновляем количество лучших
            maxstart = p[0]
    else:
        if count == maxvac:  # конец интервала с лучшим пока набором
            maxvactime += p[0] - maxstart + 1
        count -=1

print(maxvacnum, maxvactime)

БЛОГ НА HUSL

Найти алгоритм подсчета количеств множественного перекрытия интервалов, а также найти длительность таких интервалов

Ответы (1 шт):