Какой алгоритм использовать для поиска точки, охватывающей наибольшее количество интервалов, и вычислить время этой точки
Входная информация поступает из стандартного ввода, в первой строке приходит 1 число - количество вакансий. Каждая из следующих строк содержит информацию о вакансии в виде двух чисел – начальное и конечное время, они разделены пробелом. Некорректные данные на вход не поступают.
Теперь нужно определить период времени, когда открытых вакансий было больше всего.
Считаем, что:
- начальное и конечное время всегда присутствуют;
- начальное время всегда меньше или равно конечному;
- начальное и конечное время включены в интервал.
Выходные данные
В качестве ответа в стандартный вывод через пробел нужно вывести два числа: количество найденных интервалов и сумму длительности интервалов в секундах (начальная и конечная секунды должны быть включены в интервал).
Пример 1
Исходные данные: 1
1595862781 1595862785
Выходные данные: 1 5
Пример 2
Входные данные:
2
1595862781 1595862783
1595862782 1595862784
Выходные данные: 1 2
Пример 3
Входные данные:
2
1595862781 1595862782
1595862783 1595862784
Выходные данные: 2 4
Решил методом «Сканирующая прямая», но решение не проходит все тесты. Вот пример кода. Создал список с временными интервалами, отсортировал его, когда встречаем "старт" увеличиваем счетчик вакансий и сверяем с максимальным количеством вакансий, если больше устанавливаем время начала интервала, если меньше устанавливаем время конца, считаем период и добавляем в список количество вакансий и период. Какие методы актуальны для этой задачи? На каких тестах может упасть решение?
def final():
i = 0
times = []
ans = []
val = int(input())
while i < val:
start, end = input().split()
times.append((start, 0) )
times.append((end, 1))
i += 1
times = sorted(times)
vacancy = 0
maxVacancy= 0
timeStart = 0
timeEnd = 0
period = 0
for time in times:
if time[1] == 0:
vacancy += 1
if vacancy > maxVacancy:
timeStart = int(time[0])
timeEnd = -1
maxVacancy = vacancy
else:
vacancy -= 1
if vacancy < maxVacancy and timeEnd == -1:
timeEnd = int(time[0])
period = timeEnd - timeStart + 1
ans.append((maxVacancy, period))
maxVacancy = vacancy
max = ans[0][0]
time = 0
span = 0
for val in ans:
if val[0] > max:
max = val[0]
time = val[1]
span = 1
elif val[0] == max:
time += val[1]
span += 1
print(span, time)
if __name__ == '__main__':
final()
Ответы (2 шт):
Идея решения правильная.
Чтобы не запутаться, действия стоит выполнять сразу при изменении счётчика, т.е.
if time[1] == 'start':
count += 1
действия при увеличении (if count >= maxCount: ...
else:
действия при уменьшении (if count == maxCount: ...
count -= 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)
Сортировка битая. У тебя вместо чисел лежат строки и сортируются они не по возрастанию, а лексикографически.
2
2 10
5 6
[('10', 'zend'), ('2', 'start'), ('5', 'start'), ('6', 'zend')]