0

Как можно решить такую задачу?

— lesson – начало и конец урока

— pupil – интервалы присутствия ученика

— tutor – интервалы присутствия учителя

Интервалы устроены следующим образом – это всегда список из четного количества элементов. Под четными индексами (начиная с 0) время входа на урок, под нечетными - время выхода с урока. Нужно написать функцию, которая получает на вход словарь с интервалами и возвращает время общего присутствия ученика и учителя на уроке (в секундах).

Входные данные:

{ 'lesson': [1594663200, 1594666800], 

  'pupil': [1594663340, 1594663389, 1594663390, 1594663395, 1594663396, 1594666472], 

  'tutor': [1594663290, 1594663430, 1594663443, 1594666473] }

Схематично, нужный результат:

Схема алгоритма

1
  • так а что у вас не получается?
    – strawdog
    17 мар 2021 в 13:59

4 ответа 4

6

Делаете общий список, в который складываете кортежи (или списки из двух элементов), содержащие время события и признак startend, равный +1 для начала интервала, -1 для конца интервала

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

Создаёте counter = 0

Проходите по списку, для каждого элемента добавляя startend к counter

Если counter становится равным 3, запоминаете время (началось общее присутствие)

Если counter переходит из 3 в 2, вычитаете из текущего времени запомненное, прибавляете разницу к время общего присутствия ученика и учителя на уроке

Добрался до компа:

t = { 'lesson': [1594663200, 1594666800],'pupil': [1594663340, 1594663389, 1594663390, 1594663395, 1594663396, 1594666472],'tutor': [1594663290, 1594663430, 1594663443, 1594666473] }
events = []
for k in t:
    ev = t[k]
    for i in range(len(ev)):
        events.append((ev[i], 1 - 2*(i%2))) # +-1 для чётного и нечетного индекса
events.sort()
cnt = 0
start = -1
elapsedtime = 0
for e in events:
    cnt += e[1]
    if cnt == 3:
        start = e[0]
    if cnt == 2 and start > 0:
        elapsedtime += e[0] - start
        start = -1
print(elapsedtime)

>>3117
1
  • Спасибо, я вчера к вечеру все-таки сообразил как написать)
    – nortonts
    18 мар 2021 в 16:08
2

Задача решается заметанием. Различать отрезки не нужно - они все равноправны. Нужно считать только то время которое попадает в три отрезка одновременно.

Входные данные для примера:

task = {
    'lesson': [1594663200, 1594666800],
    'pupil': [1594663340, 1594663389, 1594663390, 1594663395, 1594663396, 1594666472],
    'tutor': [1594663290, 1594663430, 1594663443, 1594666473]
}

Пройдемся по всем спискам из задания и пометим их начала и концы:

def all_events(task):
    for v in task.values():
        yield from zip(v, itertools.cycle((-1, 1)))

print(*all_events(task), sep='\n')
(1594663200, -1)
(1594666800, 1)
(1594663340, -1)
(1594663389, 1)
(1594663390, -1)
(1594663395, 1)
(1594663396, -1)
(1594666472, 1)
(1594663290, -1)
(1594663430, 1)
(1594663443, -1)
(1594666473, 1)

События должны быть упорядочены по времени (можно обойтись без вызова sorted, так короче писать):

print(*sorted(all_events(task)), sep='\n')
(1594663200, -1)
(1594663290, -1)
(1594663340, -1)
(1594663389, 1)
(1594663390, -1)
(1594663395, 1)
(1594663396, -1)
(1594663430, 1)
(1594663443, -1)
(1594666472, 1)
(1594666473, 1)
(1594666800, 1)

Вторые числа в событиях суммируются. Когда сумма достигает -3 урок начинается, когда перестаёт равняться -3 урок прекращается:

событие            счётчик единиц    что происходит
                   0
(1594663200, -1)  -1
(1594663290, -1)  -2
(1594663340, -1)  -3                 урок начался
(1594663389, 1)   -2                 урок кончился
(1594663390, -1)  -3                 урок начался
(1594663395, 1)   -2                 урок кончился
(1594663396, -1)  -3                 урок начался
(1594663430, 1)   -2                 урок кончился
(1594663443, -1)  -3                 урок начался
(1594666472, 1)   -2                 урок кончился
(1594666473, 1)   -1
(1594666800, 1)    0

Функция отмечающая начала и концы уроков:

def presence_events(task):
    c_prev = 0
    for time, border in sorted(all_events(task)):
        c_next = c_prev + border
        if c_prev == -2 and c_next == -3:
            yield time, border
        if c_prev == -3 and c_next == -2:
            yield time, border
        c_prev = c_next

print(*presence_events(task), sep='\n')
(1594663340, -1)
(1594663389, 1)
(1594663390, -1)
(1594663395, 1)
(1594663396, -1)
(1594663430, 1)
(1594663443, -1)
(1594666472, 1)

Длительности уроков надо сложить. Чтобы код был проще начало урока вычетается из суммы, конец урока прибавляется к сумме:

def presence(task):
    return sum(t * b for t, b in presence_events(task))

print(presence(task))

3117

1

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

обозначим x как большее начало двух интервалов, а y как окончание меньшее окончание двух интервалов.

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

создаем функцию, которая будет исправлять наши списки пребывания ученика и учителя:

def edges_trim(arr, start, end):
    """Исправляем интервалы, которые не входят в урок.
    """
    for i in range(len(arr)):
        if arr[i] < start: arr[i] = start
        elif arr[i] > end: arr[i] = end

в функцию выше надо передать по очереди tutor и pupel вместе с lesson[0], lesson[1].

def task(pupil, tutor):
    start = tutor[0] 
    seconds = 0
    for i in range(0, len(tutor), 2):
        for j in range(0, len(pupil), 2):
            # окончание второго интервала, должно быть позже последнего
              сохраненного общего пребывания
            if start < pupil[j+1]: 
                x = max(tutor[i], pupil[j])
                y = min(tutor[i+1], pupil[j+1])
                # если наши значения не интервал, а то что мы уже учли,
                  пропускаем, мы его уже учли в предыдущих циклах
                if x > y: continue
                # в промежутке от start до x кто-то из них не был на уроке, 
                  это уже начало нового промежутка общего пребывания
                if x > start: start = x 
                seconds += y - start
                start = y 
    return seconds

в цикле будем проходить от 0 элемента до последнего с шагом 2, так у нас i-ый и j-ый элементы будут началом интервала, а i+1 и j+1 будут концами. функция выше возвращает нужное нам значение. мы будем запоминать в какую секунду в последний раз учитель и ученик были на уроке в переменной start, и отнимать от y эту переменную.

0

В итоге разобрался вчера. Вот что получилось:

def appearance(intervals):
    lesson = intervals['lesson']
    pupil = intervals['pupil']
    tutor = intervals['tutor']
    lesson_range = range(lesson[0], lesson[1]+1)
    pupil_ranges = make_ranges(pupil)
    tutor_ranges = make_ranges(tutor)
    intervals_list = []
    check_list = []
    check_list += lesson
    check_list += pupil
    check_list += tutor
    for timestump in check_list:
        if timestump in lesson_range:
            pupil_result = check_in_range(timestump, pupil_ranges)
            tutor_result = check_in_range(timestump, tutor_ranges)
            if pupil_result == True and tutor_result == True:
                intervals_list.append(timestump)
    intervals_list.sort()
    time = 0
    for i in range(1, len(intervals_list), 2):
        delta = intervals_list[i] - intervals_list[i-1]
        time += delta
    return time


def check_in_range(timestump, ranges):
    for timedelta in ranges:
        if timestump in timedelta:
            return True      


def make_ranges(intervals):
    range_list = []
    for i in range(1, len(intervals), 2):
        range_list.append(range(intervals[i-1], intervals[i]+1))
    return range_list
3
  • Подразумевается только один урок?
    – MBo
    18 мар 2021 в 16:33
  • Да, на входе всегда только один урок. Вроде где-то ошибка у меня, сейчас пытаюсь найти
    – nortonts
    18 мар 2021 в 18:31
  • Думаю, в вашем решении ошибка: ru.stackoverflow.com/a/1430614/416121 17 июл 2022 в 18:44

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.