Я пытаюсь придумать алгоритм, который всегда дает оптимальное решение этой проблемы в кратчайшие сроки:
Есть n кандидатов на работу и k комнат, в которых у них запланированы собеседования в разное время дня. У интервью есть определенное расписание в каждой комнате, при этом у каждого интервью есть определенное время начала (si), время окончания (fi) и комната для интервью (rя). Все единицы времени всегда являются целыми числами. Кроме того, нам нужно запланировать фотографии с людьми, которые в настоящее время опрашиваются в течение дня. На самом деле фотографии не занимают много времени, но в какой-то момент дня каждый интервьюируемый должен быть на фотографии. Если мы запланируем снимок на время t, все люди, у которых в настоящее время берут интервью, будут на этом изображении. Фотосъемка не влияет на оставшееся время начала и окончания каждого интервью. Итак, проблема в следующем: с неупорядоченным списком интервью, каждое с переменными (si, fi, ri), как сделать вы следите за тем, чтобы каждый кандидат на собеседование был на фотографии, при этом делая как можно меньше фотографий?
Поэтому в идеале мы должны делать снимки, когда присутствует как можно больше людей, чтобы свести к минимуму количество сделанных снимков. Моя первоначальная идея для этого была своего рода грубой силой, но это была бы действительно плохая среда выполнения. Очень важно свести к минимуму время выполнения этого алгоритма, при этом возвращая как можно меньше фотографий. При этом, если вы можете придумать быстрый жадный алгоритм, который не решает проблему идеально, я бы тоже хотел это услышать.
Я уверен, что мое описание здесь было далеко не безупречным, поэтому, если вы хотите, чтобы я что-то прояснил, не стесняйтесь оставлять комментарии, и я свяжусь с вами.
