Решение задачи Антон и занятия с Codeforces
Без пояснения   Просмотров: 56
Антону нравятся шахматы. А еще ему нравится программирование. Неудивительно, что он решил посещать занятия по шахматам и по программированию.
У Антона есть n вариантов, когда он будет заниматься шахматами, i-й вариант задается отрезком времени (l 1, i, r 1, i). Также у него есть m вариантов, когда он будет заниматься программированием, i-й вариант задается отрезком времени (l 2, i, r 2, i).
Антону необходимо выбрать ровно один из n возможных отрезков времени, когда он будет заниматься шахматами и ровно один из m возможных отрезков времени, когда он будет заниматься программированием. Ему хочется побольше отдохнуть между занятиями, поэтому из всех возможных пар отрезков он хочет выбрать ту, расстояние между отрезками в которой как можно больше.
Расстоянием между двумя отрезками (l 1, r 1) и (l 2, r 2) будем называть минимально возможное расстояние между точкой на первом отрезке и точкой на втором отрезке, то есть минимально возможное |i - j|, где l 1 ≤ i ≤ r 1 и l 2 ≤ j ≤ r 2. В частности, если отрезки пересекаются, то расстояние между ними равно 0.
Антону интересно, сколько времени он сможет отдохнуть между занятиями в лучшем случае. Помогите ему найти это число!
У Антона есть n вариантов, когда он будет заниматься шахматами, i-й вариант задается отрезком времени (l 1, i, r 1, i). Также у него есть m вариантов, когда он будет заниматься программированием, i-й вариант задается отрезком времени (l 2, i, r 2, i).
Антону необходимо выбрать ровно один из n возможных отрезков времени, когда он будет заниматься шахматами и ровно один из m возможных отрезков времени, когда он будет заниматься программированием. Ему хочется побольше отдохнуть между занятиями, поэтому из всех возможных пар отрезков он хочет выбрать ту, расстояние между отрезками в которой как можно больше.
Расстоянием между двумя отрезками (l 1, r 1) и (l 2, r 2) будем называть минимально возможное расстояние между точкой на первом отрезке и точкой на втором отрезке, то есть минимально возможное |i - j|, где l 1 ≤ i ≤ r 1 и l 2 ≤ j ≤ r 2. В частности, если отрезки пересекаются, то расстояние между ними равно 0.
Антону интересно, сколько времени он сможет отдохнуть между занятиями в лучшем случае. Помогите ему найти это число!