Отправлено: 18.02.24 16:55. Заголовок: Задача 26-6794 не сходится половина ответа

Условие задачи
(№ 6794) (А. Рогов) В отделении банка используется система распознавания лиц, с помощью которой фиксируется время, когда посетитель пришел в отделение и время, когда он вышел. Для удобства время хранится как целое число, показывающее, сколько секунд прошло от начала суток до события. Посетителей банка обслуживают операторы, которые пронумерованы, начиная с 1. Посетитель обслуживается свободным оператором с минимальным номером. Оператор может принять следующего посетителя в ту же секунду, как обслуживаемый им посетитель покидает здание. На обслуживание требуется, как минимум, одна секунда. Если свободных операторов нет, посетитель становится в очередь. Посетитель может не дождаться своей очереди и уйти.
Определите, сколько посетителей было обслужено операторами и номер оператора, обслужившего последнего посетителя.
...
Моя программа

 
 f=open('26-132.txt') 
 n,k=map(int,f.readline().split()) 
 D=[] 
 for line in f.readlines(): 
     t,tend = line.split() 
     D+=[(int(t),int(tend))] 
 f.close() 
 oper=k*[0]   # время освобождения операторов 
 D.sort(key=lambda x : x[0]) 
 count=0 
 for t, tend in D: 
     tmin=min(oper) 
     imin=oper.index(tmin) 
     if tmin<tend: 
         count+=1 
         oper[imin]=tend 
         last=imin 
 print(count,last+1)   
 

Результат: 2108 177. Количество обслуженных посетителей совпало с ответом, а номер оператора - нет. В авторском решении моделируется очередь, я этого не делаю, но ведь и так после сортировки по времени прихода посетители попадают к оператору в порядке очереди! Что я не учёл? Кто может подсказать? Кстати, на тестовом варианте исходных данных программа получила правильный результат.

 Отправлено: 27.02.24 14:34. Заголовок: Вероятно ошибка как ..

Вероятно ошибка как раз в том, что нет очереди.
Прилагаю свой вариант решения:

with open('Files/26-132.txt') as f: 
     n, k = tuple(map(int, f.readline().split())) 
     visitors = sorted([tuple(map(int, x.split())) for x in f]) 
     operators = [-1] * k 
     queue = [] 
     last = 0 
     count = 0 
     events_log = [] 
  
     # Заполним лог событий 
     for i in range(len(visitors)): 
         arrive, leave = visitors 
         events_log.append((arrive, 1, i))  # 1 пришел 
         events_log.append((leave, -1, i))  # -1 ушел 
  
     # Сортировка лога по времени события 
     events_log.sort() 
  
     # Перебор событий 
     for event in events_log: 
         # Пришел посетитель 
         if event[1] > 0: 
             # Добавить в очередь 
             queue.append(event) 
         # Ушел посетитель 
         else: 
             try: 
                 # Освободить оператора, если посетитель был у него на приеме 
                 operators[operators.index(event[2])] = -1 
             except ValueError: 
                 # Если у оператора не найден, то удалить из очереди 
                 for q in queue: 
                     if q[2] == event[2]: 
                         queue.remove(q) 
                         break 
                 # Когда ушел из очереди оператор не освободился 
                 continue 
  
         # Распределить посетителей из очереди по операторам 
         for i in range(operators.count(-1)): 
             if len(queue): 
                 count += 1 
                 last = operators.index(-1) 
                 operators[last] = queue.pop(0)[2]  # Опреатору записать номер посетителя 
             else: 
                 break 
  
     print(count, last + 1)

 Отправлено: 28.02.24 13:01. Заголовок: Вот еще вариант кода..

Вот еще вариант кода:

 
 f=open('26-132.txt') 
 [n,k]=list(map(int,f.readline().split())); print(n,k) 
 s=[list(map(int,c.split())) for c in f.readlines()] 
 kol=0; op=[0]*k 
 while s: 
     s=sorted([c for c in s if c[1]>min(op)])  # сортируем клиентов, которым есть смысл дожидаться очереди  
     c=s[0]  # время первого в очереди клиента  
     minop=min(op)  # время ближайшего освобождения оператора 
     for i in range(len(op)): 
         if minop > c[0]: s[0][0]=min(op)   # если все заняты, то ждем первого освободившегося 
         if op<=c[0]: 
             op=c[1]; s.remove(c)  # если кто-то свободен, то идем к нему (и исчезаем из очереди) 
             kol+=1; print(f'обслужено клиентов:{kol}, последний обслуженный № { i+1}, {c}') 
             break 
 

 Отправлено: 28.02.24 13:46. Заголовок: Если долго мучиться, то ... решение найдется!

Меня всё время мучил вопрос, зачем нужна очередь, если посетители и так стоят в очереди. Наконец, я понял, в чём моя ошибка. Я назначал очередному посетителю того оператора, который освободится первым (первого по времени), но не учел, что если к моменту прихода посетителя есть несколько свободных операторов, то из них нужно выбрать первого по номеру.
Привожу исправленный вариант программы, который получает нужный результат, но не использует структуру очереди.

 
 f=open('26-132.txt') 
 n,k=map(int,f.readline().split()) 
 D=[] 
 for line in f.readlines(): 
     t,tend = line.split() 
     D+=[(int(t),int(tend))] 
 f.close() 
 oper=k*[0]   # время освобождения операторов 
 D.sort() 
 count=0 
 for t, tend in D: 
     tmin=min(oper) 
     if tmin<=t:    # выбираем "минимального" из свободных операторов 
         V=[j for j in range(k) if tmin<=oper[j]<=t] 
         imin=min(V) 
         count+=1 
         oper[imin]=tend 
         last=imin 
     elif tmin<tend:   # выбираем того, кто первый освободится 
         imin=oper.index(tmin) 
         count+=1 
         oper[imin]=tend 
         last=imin 
 print(count,last+1)