Алгоритмы заметающей прямой

@ruletik · Регистрация: 08.12.2015

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

Задание
Реализовать "Алгоритмы заметающей прямой". Считать количество клиентов, для каждого клиента считать время прихода и ухода. Найти наибольшее количество одновременно присутствующих клиентов.

Пыталась следовать следующему алгоритму:
1. Генерируешь случайное число N (человек).
2. Генерируешь два массива A(),B() - времена прихода, времена ухода. Индекс - номер человека.
3. Делаешь слияние массивов в один C(), параллельно создавая второй массив D() - его значения будут +1 (приход) или -1 (уход). Индексы массивов совпадают - это номер человека.
4. Сортируешь массив по возрастанию времени, попутно переставляя индексы обоих массивов.
Теперь по индексу легко отследить хронологию.
5. Создаешь еще массив E() (значение = кол-ву находящихся в музее человек). Индекс совпадает с индексами предыдущих массивов. Значения последовательно складываешь из значений массива D().
6. Находишь максимальное число в массиве D().

4 пункта выполнила, но на 5 застряла. Помогите, пожалуйста, закончить мой код

Сам код:

Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input()) # число клиентов
a = [] # время прихода
b = [] # время ухода
for i in range(n): 
  a.append(int(input())) 
for i in range(n): 
  b.append(int(input()))
c = [0]*(2*n)
c = a + b # слияние массивов
d = [1]*n + [-1]*n
for i in range(len(c)-1): # сортировка методом пузырька 
    for j in range(len(c)-i-1):
      if c[j] > c[j+1]:
        c[j], c[j+1] = c[j+1], c[j]
        d[j], d[j+1] = d[j+1], d[j]

@eaa · 24.04.2020, 19:22

сначало слить потом сортировать?

@ruletik · 24.04.2020, 19:25 **[ТС]**

eaa, да

@eaa · 25.04.2020, 07:53

Python
1
2
3
4
5
6
7
8
9
n = int(input())
a = []
for _ in range(n):
    begin, end = map(int, input().split())
    a.append((begin,'b'))
    a.append((end,'e'))
print(a)
a.sort()
print(*[y for x,y in a], sep='')

Code
1
2
3
4
5
6
7
4
1 2
2 3
2 4
4 5
[(1, 'b'), (2, 'e'), (2, 'b'), (3, 'e'), (2, 'b'), (4, 'e'), (4, 'b'), (5, 'e')]
bbbeebee

@ruletik · 25.04.2020, 09:28 **[ТС]**

а как посчитать наибольшее количество одновременно присутствующих клиентов?

@eaa · 25.04.2020, 09:56

алгоритм понятен?

@ruletik · 25.04.2020, 10:04 **[ТС]**

eaa, ваш код мне понятен (вы сократили мое решение, только я значение массивов c и d попарно не объединяла). А вот по алгоритму, которому я следовала, 5 пункт непонятен. Что вот дальше делать?

@eaa · 25.04.2020, 10:11

5,6 пункт там написана какая то ерунда.
хотя понятно откуда это. это из другого способа решения, где интервал разбивается на секунды и к каждой секунде прибавляют 1.

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

@ruletik · 25.04.2020, 10:31 **[ТС]**

eaa, спасибо большое, сейчас попробую)

@eaa · 25.04.2020, 11:25

вообще лучше сначала отсортировать оба списка, а потом считать при слиянии сразу максимум.

@ruletik · 25.04.2020, 12:30 **[ТС]**

eaa, я сначала только с двумя работала списками и их сортировала, но преподаватель сказал, что сортировать нужно именно объединенный список((

у меня, кстати, получилось так, как вы посоветовали

Новые блоги и статьи Все статьи Все блоги /
Переходник USB-CAN-GPIO Eddy_Em 20.03.2026 Достаточно давно на работе возникла необходимость в переходнике CAN-USB с гальваноразвязкой, оный и был разработан. Однако, все меня терзала совесть, что аж 48-ногий МК используется так тупо: просто. . .	Оттенки серого Argus19 18.03.2026 Оттенки серого Нашёл в интернете 3 прекрасных модуля: Модуль класса открытия диалога открытия/ сохранения файла на Win32 API; Модуль класса быстрого перекодирования цветного изображения в оттенки. . .	SDL3 для Desktop (MinGW): Рисуем цветные прямоугольники с помощью рисовальщика SDL3 на Си и C++ 8Observer8 17.03.2026 Содержание блога Финальные проекты на Си и на C++: finish-rectangles-sdl3-c. zip finish-rectangles-sdl3-cpp. zip	Символические и жёсткие ссылки в Linux. algri14 15.03.2026 Существует два типа ссылок — символические и жёсткие. Ссылка в Linux — это запись в каталоге, которая может указывать либо на inode «файла-ИСТОЧНИКА», тогда это будет «жёсткая ссылка» (hard link),. . .
[Owen Logic] Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ФедосеевПавел 14.03.2026 Поддержание уровня воды в резервуаре количеством включённых насосов: моделирование и выбор регулятора ВВЕДЕНИЕ Выполняя задание на управление насосной группой заполнения резервуара,. . .	делаю науч статью по влиянию грибов на сукцессию anaschu 13.03.2026 прикрепляю статью	SDL3 для Desktop (MinGW): Создаём пустое окно с нуля для 2D-графики на SDL3, Си и C++ 8Observer8 10.03.2026 Содержание блога Финальные проекты на Си и на C++: hello-sdl3-c. zip hello-sdl3-cpp. zip Результат:	Установка CMake и MinGW 13.1 для сборки С и C++ приложений из консоли и из Qt Creator в EXE 8Observer8 10.03.2026 Содержание блога MinGW - это коллекция инструментов для сборки приложений в EXE. CMake - это система сборки приложений. Здесь описаны базовые шаги для старта программирования с помощью CMake и. . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	24.04.2020, 19:22
	сначало слить потом сортировать? 0

@ruletik 2 / 2 / 0 Регистрация: 08.12.2015 Сообщений: 210
	24.04.2020, 19:25 [ТС]
	eaa, да 0

@ruletik 2 / 2 / 0 Регистрация: 08.12.2015 Сообщений: 210
	25.04.2020, 09:28 [ТС]
	а как посчитать наибольшее количество одновременно присутствующих клиентов? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.04.2020, 09:56
	алгоритм понятен? 0

@ruletik 2 / 2 / 0 Регистрация: 08.12.2015 Сообщений: 210
	25.04.2020, 10:04 [ТС]
	eaa, ваш код мне понятен (вы сократили мое решение, только я значение массивов c и d попарно не объединяла). А вот по алгоритму, которому я следовала, 5 пункт непонятен. Что вот дальше делать? 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.04.2020, 10:11
	5,6 пункт там написана какая то ерунда. хотя понятно откуда это. это из другого способа решения, где интервал разбивается на секунды и к каждой секунде прибавляют 1. для того чтобы найти наибольшее количество одновременно присутствующих, нужно найти наибольшее количество подряд идущих b. 1

@ruletik 2 / 2 / 0 Регистрация: 08.12.2015 Сообщений: 210
	25.04.2020, 10:31 [ТС]
	eaa, спасибо большое, сейчас попробую) 0

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	25.04.2020, 11:25
	вообще лучше сначала отсортировать оба списка, а потом считать при слиянии сразу максимум. 0

@ruletik 2 / 2 / 0 Регистрация: 08.12.2015 Сообщений: 210
	25.04.2020, 12:30 [ТС]
	eaa, я сначала только с двумя работала списками и их сортировала, но преподаватель сказал, что сортировать нужно именно объединенный список(( у меня, кстати, получилось так, как вы посоветовали 0