1

Тема: Прийом у директора задача з e-olymp

Задача - https://www.e-olymp.com/uk/contests/4237/problems/33836 (вибачте за російську)
Мій код:

list_x = []
time = []
for i in range(int(input())):
    list_1 = list(map(int, ":".join(input().split()).split(":")))
    time.append([list_1[0] * 60 + list_1[1], list_1[2] * 60 + list_1[3]])
print(time)

Поки що зробив лише масив з часом, переведеним в хвилини.
Далі розумію, що потрібно буде відсортувати масив і так перевірити, чи час прийому не перетинається.
Проблема в тому, що не знаю як це реалізувати.
Буду вдячним за допомогу.

2

Re: Прийом у директора задача з e-olymp

а стандартний модуль datetime заборонено використовувати?

Подякували: Eff1c1

3 Востаннє редагувалося koala (18.01.2019 08:27:25)

Re: Прийом у директора задача з e-olymp

ping, а чим вам тут datetime допоможе? Зекономить пару символів при розборі стрічки?

Не буду звертати увагу на мову та певну невизначеність (час прийому - протягом доби, а питають лише про тих, хто протягом робочого дня).
Це, швидше за все, overthinking, і можна якось простіше; ключовий момент в задачі - не час зустрічі, а саме перетини, тобто задача більше на графи. Зараз я бачу щось таке:
1. Вводимо всіх відвідувачів, нумеруємо, сортуємо події (початок-кінець) за часом.
2. Ідемо по списку за часом з початку, запам'ятовуємо всіх поточних кандидатів (тобто тих, в кого зустріч уже могла б початися і ще не закінчилася), записуємо в них список перетинів (в кожного кандидата має бути список з номерів інших кандидатів, час зустрічі яких накладається; коли доходимо до часу початку зустрічі з кандидатом, цей список в нього очищується від попередніх записів і туди додаються всі поточні кандидати, а до всіх поточних - він).
3. Коли в когось закінчилася зустріч, перевіряємо такі ознаки:
- якщо в нього 0 перетинів - виключаємо його зі списку і додаємо 1 до результату (його приймаємо), продовжуємо;
- якщо в нього 1 перетин - виключаємо його й того, з ким у нього перетин, зі списку і додаємо 1 до результату (його приймаємо, іншого ні - все одно когось доведеться виключити, а цей точно більше ні з ким не перетинається); переходимо на п.2.
- якщо посеред співбесіди немає інших подій (початків та кінців зустрічей), то всіх кандидатів, що накладаються на цю співбесіду, видаляємо і додаємо 1 до результату (його приймаємо, інших ні - з них усіх має залишитися один, а цей точно найменше контактує з іншими); переходимо на п.2.
4. Якщо дійшли до кінця, а кандидати ще є, знаходимо того, в кого найбільше перетинів (будь-якого) і видаляємо, переходимо на п.2
5. PROFIT.

Повертатися можна і не так далеко назад, але мені зараз ліньки продумувати; та й, зрештою, я ж кажу - мені здається, має бути простіший алгоритм.
В принципі, заголовок (про жадібність) натякає, що з кожної накладки слід лишати того, чия співбесіда раніше закінчується, і цього достатньо.

Подякували: Eff1c, PRY2

4

Re: Прийом у директора задача з e-olymp

«Дерево проміжків» (Interval tree), побудоване на основі червоно-чорного дерева, описане в розділі 14 «Доповнення структур даних» третього видання CLRS.
Втім, згоден з koala, заголовок натякає на простіший алгоритм.

Подякували: leofun01, Eff1c, PRY3

5

Re: Прийом у директора задача з e-olymp

може щось таке (на там нема обробки вхідних даних - то вже лінь писати було):

from datetime import time
from pprint import pprint

visitors = [
    {
        'id': 10,
        'start_time': time(9, 10),
        'end_time': time(13, 5),
        'conflicts_with': []
    },
    {
        'id': 15,
        'start_time': time(14, 0),
        'end_time': time(14, 26),
        'conflicts_with': []
    },
    {
        'id': 20,
        'start_time': time(14, 20),
        'end_time': time(15, 15),
        'conflicts_with': []
    },
    {
        'id': 30,
        'start_time': time(14, 25),
        'end_time': time(14, 30),
        'conflicts_with': []
    },
    {
        'id': 40,
        'start_time': time(15, 0),
        'end_time': time(17, 0),
        'conflicts_with': []
    }
]


active_visitors = []

for v in visitors:
    for a in active_visitors.copy():
        if v['start_time'] < a['end_time']:
            a['conflicts_with'].append(v['id'])
            v['conflicts_with'].append(a['id'])
        else:
            active_visitors.remove(a)

    active_visitors.append(v)


for v in sorted(visitors, key=lambda x: len(x['conflicts_with']), reverse=True):
    if len(v['conflicts_with']):
        for _id in v['conflicts_with']:
            another_cand = [x for x in visitors if x['id'] == _id][0]
            another_cand['conflicts_with'].remove(v['id'])

        visitors.remove(v)

print(len(visitors))

перевірив на кільокх варіантах - ніби працює

Подякували: Eff1c1

6 Востаннє редагувалося koala (18.01.2019 14:40:57)

Re: Прийом у директора задача з e-olymp

volodymyrko, там до 1000 візіторів і 1 секунда часу. Точно вкладетеся?

for v in sorted...:
    ....
    for _id in v['conflicts_with']:
        ....[x for x in visitors if x['id'] == _id][0]

- три вкладених цикли. Хоч би на next замінили, чи що...

Подякували: Eff1c1

7 Востаннє редагувалося volodymyrko (18.01.2019 16:51:27)

Re: Прийом у директора задача з e-olymp

та там і  next не допоможе..  (про "час" і "память" я зовсім.. забув..)
локаьно спробував всі list-и на dict-и змінити  - результат менше 0.3 сек (на 1000 айтемах). якщо мамиму час і трошки код причесу - то викладу

Подякували: Eff1c, PRY2

8

Re: Прийом у директора задача з e-olymp

Поняв, що ця задача мені поки не по зубах.
Вернусь до неї пізніше.
Дякую

9

Re: Прийом у директора задача з e-olymp

мій варіант зі словниками

import random
from datetime import datetime, timedelta


def func(visitors):
    active_visitors = []

    for ind in sorted(visitors):
        v = visitors[ind]
        for ind_a in active_visitors.copy():
            active_visitor = visitors[ind_a]

            if v['start_time'] < active_visitor['end_time']:
                active_visitor['conflicts_with'].append(ind)
                v['conflicts_with'].append(ind_a)
            else:
                active_visitors.remove(ind_a)

        active_visitors.append(ind)

    for ind in sorted(visitors, key=lambda x: len(visitors[x]['conflicts_with']), reverse=True):
        v = visitors[ind]

        if len(v['conflicts_with']):
            for _id in v['conflicts_with']:
                another_cand = visitors[_id]
                another_cand['conflicts_with'].remove(ind)

            del visitors[ind]


def gen_time_pairs():
    total_seconds = 9 * 60 * 60  # 32400 seconds between 9:00-18:00
    nine_o_clock = datetime(2019, 1, 21, 9, 0)

    time_pairs = []
    for _ in range(1000):
        t1 = random.randint(0, total_seconds)
        t2 = random.randint(0, total_seconds)

        assert t1 != t2, 'test data failed, re-run script'

        if t1 > t2:
            t1, t2 = t2, t1

        start_time = nine_o_clock + timedelta(seconds=t1)
        end_time = nine_o_clock + timedelta(seconds=t2)

        time_pairs.append((start_time, end_time))

    return time_pairs


def gen_visitors(time_pairs):
    res_visitors = {}
    ind = 0

    for start_time, end_time in sorted(time_pairs, key=lambda x: x[0]):
        res_visitors[ind] = {
            'start_time': start_time,
            'end_time': end_time,
            'conflicts_with': []
        }
        ind += 1

    return res_visitors

time_pairs = gen_time_pairs()
visitors = gen_visitors(time_pairs)
func(visitors)

print(len(visitors))

time  каже, що в то займає в районі 0.5-0.7сек  (принаймі в мене ))  ) і памяті ніби небагато..

Подякували: Eff1c1

10

Re: Прийом у директора задача з e-olymp

попередній варіант (та й підхід) таки не досканалий.. час від часу виниає ситуації коли є кілька потенційний кандитатів з однакової к-тю "конфліктів" і хз кого треба видаляти (ну або прораховувати всі можливі)..

придумав ще один варіант:

import random
from datetime import datetime, timedelta


def gen_time_pairs():
    total_seconds = 9 * 60 * 60  # 32400 seconds between 9:00-18:00
    nine_o_clock = datetime(2019, 1, 21, 9, 0)

    time_pairs = []
    for _ in range(1000):
        t1 = random.randint(0, total_seconds)
        t2 = random.randint(0, total_seconds)

        assert t1 != t2, 'test data failed, re-run script'

        if t1 > t2:
            t1, t2 = t2, t1

        start_time = nine_o_clock + timedelta(seconds=t1)
        end_time = nine_o_clock + timedelta(seconds=t2)

        time_pairs.append((start_time, end_time))

    return time_pairs


def gen_visitors(time_pairs):
    res_visitors = {}
    ind = 0

    for start_time, end_time in sorted(time_pairs, key=lambda x: x[0]):
        res_visitors[ind] = {
            'start_time': start_time,
            'end_time': end_time,
            'conflicts_with': []
        }
        ind += 1

    return res_visitors


def func_2(visitors):
    tree = []

    for ind in sorted(visitors):
        v = visitors[ind]

        if tree:
            last = tree[-1]
            if v['start_time'] >= last['end_time']:
                tree.append(v)

            elif v['end_time'] < last['end_time']:
                tree.remove(last)
                tree.append(v)

        else:
            tree.append(v)

    return tree


time_pairs = gen_time_pairs()
visitors = gen_visitors(time_pairs)

result = func_2(visitors)
print('number', len(result))

як мінімум працює краще: і точніше і набагто швидше

Подякували: Eff1c1