Задачка на пересечение интервалов

@Ro Ma · Регистрация: 12.01.2020

Студворк — интернет-сервис помощи студентам

Ребят помогите пожалуйста советом как решить задачу, 2 дня без сна...
________________________________________ _____________________
Коля хочет собрать друзей у себя, чтобы решить, куда они поедут отдыхать в выходные. В компании Коли полная демократия, решение принимается большинством голосов. Среди друзей есть очень ленивые люди, и они доверили свой голос кому-то из компании. Каждый написал Коле промежутки времени, когда он сможет явиться в единую точку голосования и сколько людей ему доверили проголосовать за них. Друзья у Коли работают очень слаженно и могут принять решение за очень маленький промежуток времени, даже когда один из них только явился на встречу, а второй уже будет уходить.
Помогите Коле понять, какое максимальное количество голосов он сможет собрать, если выберет оптимальное время.
На вход подается файл, где в первой строке написано количество друзей, от которых поступила информация. В каждой следующей строке имеется информация про одного друга Коли через пробел: время, когда он сможет прийти, время, когда ему нужно будет уходить, сколько друзей доверили ему свой голос. Все числа целые, неотрицательные и меньше 32 767.
На выходе нужно вывести максимальное количество голосов, которое сможет собрать Коля, выбрав оптимальное время.
Мое решение такое:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
n = int(input('количество друзей: '))
s = []
A = []
B = []
my_friends = range(n)
for i in my_friends:
    a = int(input('время прихода: '))
    b = int(input('время ухода: '))
    c = int(input('количество голосов: '))
    if i == 0:
        A.append(a)
        B.append(b)
        if c == 0:
            s.append(1)
        else:
            s.append(1 + c)
    else:
        if b >= min(A) and a <= max(B):
            A.append(a)
            B.append(b)
            if c == 0:
                s.append(1)
            else:
                s.append(1 + c)
        else:
            continue
print(sum(s))

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

@__ALPHA__ · 13.01.2020, 00:29

Не проверял:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
n = int(input('Количество друзей: '))
 
s = []
 
#Первый шаг вне цикла (a=min, b=max, c=count, a<=b)
a, b, c = map(int, input(f'Информация по 1-му другу: ').split())
s.append( (a, b, c) )
range_min = a
range_max = b
 
for i in range(n - 1):
    a, b, c = map(int, input(f'Информация по {i+2}-му другу: ').split())
    s.append( (a, b, c) )
    range_min = min(a, range_min)
    range_max = max(b, range_max)
 
MAX = 0
current = 0
_next = 0
for i in range(range_min, range_max + 1):
    current -= _next
    _next = 0
    
    for a, b, c in s:
        if i == a:
            current += c
        if i == b:
            _next += c
 
    MAX = max(MAX, current)
    
print(MAX)

@eaa · 13.01.2020, 07:39

Ro Ma, примеры входных/выходных данных?

@Ro Ma · 22.01.2020, 20:27 **[ТС]**

eaa, вот пример... на 7 гостях с указанными интервалами должен выдавать по идее 9 итог но выдает 12, так как если происходит любое соприкосновение интервалов то он считает голоса суммарно, а нужно только тех голоса считать кто в максимальный канал перекрытия инрвалов попадает - стрелкой указал на картинке

@Ro Ma · 22.01.2020, 20:28 **[ТС]**

предложенный код работает но не правильно считает

@eaa · 22.01.2020, 21:05

примеры входных/выходных данных?
время в чем в часах/минутах/секундах?

@Ro Ma · 22.01.2020, 21:13 **[ТС]**

данные на вход поступают целыми числами, нет разницы минуты/часы... хоть в наносекундах. есть просто целочисленные интервалы (начало и конец, включительно) и целое число голосов которые собой (помимо своего) несет гость... таким образом входные данные ( пример):
6 11 0
4 6 1
6 11 0
1 3 1
3 6 2
9 14 0
6 7 1

На выходе должно быть 9!

@eaa · 22.01.2020, 21:24

Python
1
2
3
4
5
6
7
n = int(intput())
time = [0]*32767
for _ in range(n):
    a, b, c = map(int, input().split())
    for i in range(a, b+1):
        time[i] += c + 1
print(max(time))

так что ли?

@Ro Ma · 22.01.2020, 21:50 **[ТС]**

чёт не то....ввожу 3 друзей с пересекающимися в 1 точке интервалами - выдает 4, и по другим примерам тож не то.... но при этом по тем данным что дал непонятно как выдает 9.... например на вход

3 друзей
1 3 1
3 6 1
9 14 0

выдает 4...согласен...у первых 2 в точке "3" пересеклись интервалы и код сложил (1+1)+(1+1). НО...

3 друзей

1 3 1
4 6 1
9 14 0

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

И еще есть загвостка.... 2 интервала (7-14) и (15-21) они "соприкасаются" в точке перехода от 14 к 15...в условии задачи об этом говорится что мол " друзья в дверях столкнулись" и это тоже должно считаться за касание интервалов и должны считаться голоса таких....короже нюанс на нюансе....

@eaa · 22.01.2020, 22:01

все же правильно выводит.
как интервалы (7-14) и (15-21) могут пересекаться? один ушел в 14, другой пришел в 15, они не встретятся.

@Ro Ma · 22.01.2020, 22:06 **[ТС]**

Сообщение от Ro Ma

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

...я это из задачи понял именно так как написал выше... но тем не менее у меня осталось пару вопросов:

1 вопрос)
на вход
3 друзей

1 3 1
4 6 1
9 14 0

выдал 2..... почему 2? интервалы вообще ни у одного из 3х не пересеклись? должно же тогда быть 1!?
2 вопрос)
что означает в твоем коде строка:
time = [0]*32727
и что ты с ней делаешь когда time[i] += c + 1?
и огромное спасибо за помощь. твой код самый рабочий

@eaa · 22.01.2020, 22:09

Сообщение от Ro Ma

почему 2?

потому что у 1го и 2го по 2 голоса.

Новые блоги и статьи Все статьи Все блоги /
Модель ЗдрввоСохранения 7: больше работников, больше ресурсов. anaschu 08.04.2026 работников и заданий может быть сколько угодно, но настроено всё так, что используется пока что только 20% kYBz3eJf3jQ	Дальние перспективы сервера - слоя сети с космологическим дизайном интефейса карты и логики. Hrethgir 07.04.2026 Дальнейшее ближайшее планирование вывело к размышлениям над дальними перспективами. И вот тут может быть даже будут нужны оценки специалистов, так как в дальних перспективах всё может очень сильно. . .	Горе от ума kumehtar 07.04.2026 Эта мне ментальная установка, что вот прямо сейчас, мол, мне для полного счастья не хватает (нужное вписать), и когда я этого достигну - тогда и полный кайф. Одна из самых сильных ловушек на пути. . . .	Использование значений реквизитов справочника в документе, с определенными условиями и правами Maks 07.04.2026 1. Контроль срока действия договора Алгоритм из решения ниже реализован на примере нетипового документа "ЗаявкаНаРаботу", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если. . .
Доступность команды формы по условию Maks 07.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "СписаниеМатериалов", разработанного в конфигурации КА2. Задача: сделать доступной кнопку (команда формы "ЗавершитьСписание") при. . .	Уведомление о неверно выбранном значении справочника Maks 06.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "НарядПутевка", разработанного в конфигурации КА2. Задача: уведомлять пользователя, если в документе выбран неверный склад. . .	Установка Qt Creator для C и C++: ставим среду, CMake и MinGW без фреймворка Qt 8Observer8 05.04.2026 Среду разработки Qt Creator можно установить без фреймворка Qt. Есть отдельный репозиторий для этой среды: https:/ / github. com/ qt-creator/ qt-creator, где можно скачать установщик, на вкладке Releases:. . .	AkelPad-скрипты, структуры, и немного лирики.. testuser2 05.04.2026 Такая программа, как AkelPad существует уже давно, и также давно существуют скрипты под нее. Тем не менее, прога живет, периодически что-то не спеша дополняется, улучшается. Что меня в первую очередь. . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	13.01.2020, 07:39
	Ro Ma, примеры входных/выходных данных? 0

@Ro Ma 0 / 0 / 0 Регистрация: 12.01.2020 Сообщений: 6
	22.01.2020, 20:27 [ТС]
	eaa, вот пример... на 7 гостях с указанными интервалами должен выдавать по идее 9 итог но выдает 12, так как если происходит любое соприкосновение интервалов то он считает голоса суммарно, а нужно только тех голоса считать кто в максимальный канал перекрытия инрвалов попадает - стрелкой указал на картинке Миниатюры 0

@Ro Ma 0 / 0 / 0 Регистрация: 12.01.2020 Сообщений: 6
	22.01.2020, 20:28 [ТС]
	предложенный код работает но не правильно считает 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	22.01.2020, 21:05
	примеры входных/выходных данных? время в чем в часах/минутах/секундах? 0

@Ro Ma 0 / 0 / 0 Регистрация: 12.01.2020 Сообщений: 6
	22.01.2020, 21:13 [ТС]
	данные на вход поступают целыми числами, нет разницы минуты/часы... хоть в наносекундах. есть просто целочисленные интервалы (начало и конец, включительно) и целое число голосов которые собой (помимо своего) несет гость... таким образом входные данные ( пример): 6 11 0 4 6 1 6 11 0 1 3 1 3 6 2 9 14 0 6 7 1 На выходе должно быть 9! 0

@Ro Ma 0 / 0 / 0 Регистрация: 12.01.2020 Сообщений: 6
	22.01.2020, 21:50 [ТС]
	чёт не то....ввожу 3 друзей с пересекающимися в 1 точке интервалами - выдает 4, и по другим примерам тож не то.... но при этом по тем данным что дал непонятно как выдает 9.... например на вход 3 друзей 1 3 1 3 6 1 9 14 0 выдает 4...согласен...у первых 2 в точке "3" пересеклись интервалы и код сложил (1+1)+(1+1). НО... 3 друзей 1 3 1 4 6 1 9 14 0 выдал 2..... почему 2, хотя исходя из визуального представления должен был 1 т.к. ни одного перекрытия интервалов нет . И еще есть загвостка.... 2 интервала (7-14) и (15-21) они "соприкасаются" в точке перехода от 14 к 15...в условии задачи об этом говорится что мол " друзья в дверях столкнулись" и это тоже должно считаться за касание интервалов и должны считаться голоса таких....короже нюанс на нюансе.... 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	22.01.2020, 22:01
	все же правильно выводит. как интервалы (7-14) и (15-21) могут пересекаться? один ушел в 14, другой пришел в 15, они не встретятся. 0

Опции темы