e-olymp 497. Лентяй

Задача

Студент Валера являет собой классический пример лентяя. На занятия он практически не ходит, и только в конце семестра появляется в университете и сдает ”хвосты”. Его заветная мечта: найти такой день, когда можно будет сдать сразу все долги. У него есть расписание работы преподавателей, из которого точно известно, с какого и по какой день месяца каждый преподаватель ежедневно будет доступен. Помогите Валере написать программу, которая по расписанию будет определять, сможет ли Валера сдать все долги за один день или нет.

Входные данные:
Первая строка содержит количество тестов. Каждый тест состоит из количество предметов $n$ $(1 \le n \le 100)$, которые нужно сдать Валере. Далее идет $n$ строк, каждая из которых состоит из двух чисел $a$ и $b$ $(1 \le a \le b \le 31)$, задающих интервал работы очередного преподавателя.

Выходные данные:
Для каждого теста вывести в отдельной строке "YES" если возможно встретить всех преподавателей за один день, или "NO", если это невозможно.

Тесты

Входные данные Вывод программы
2
1
1 2
2
1 2
3 4
YES
NO
1
1
5 6
YES
2
2
1 4
7 9
3
1 30
2 5
5 10
NO
YES

Решение

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

Для нахождения пересечения двух отрезков нужно посчитать максимум из левых концов: $l$ и минимум из правых: $r$, тогда если $l > r$, то пересечения нет, иначе $[l; r]$ — искомое пересечение.

Теперь нам надо последовательно находить пересечение текущего пересечения и нового отрезка, для этого просто посчитаем l — максимальный из левых концов отрезков и r — минимальный из правых. Если $l > r$ то ответ "YES", иначе "NO".

Код

Ссылки

Задача на E-Olymp
Код на IdeOne
Засчитанное решение на E-Olymp

Добавить комментарий