Единственное различие между двумя версиями задачи заключается в том, учитываются ли пересечения во всех точках или только в целых точках.
Легендарная мифическая птица Симург отвечает за охрану обширных земель, и для этой цели она наняла \(n\) бдительных воинов. Каждый воин находится в боевой готовности в течение определенного отрезка времени \([l_i, r_i]\), где \(l_i\) — время начала (включительно), а \(r_i\) — время окончания (включительно), оба являются целыми положительными числами.
Один из доверенных советников Симурга, Зал, обеспокоен тем, что если несколько воинов будут караулить в одно и то же время и будут одеты в один и тот же цвет, они могут стать неотличимыми, что вызовет путаницу в дозоре. Чтобы предотвратить это, всякий раз, когда несколько воинов находятся на страже в один и тот же целый момент времени, должен быть хотя бы один цвет, который носит ровно один воин.
Таким образом, ваша задача состоит в том, чтобы определить минимальное необходимое количество цветов и назначить цвет \(c_i\) каждому отрезку дозора воина \([l_i, r_i]\) таким образом, чтобы для каждого (целого) момента времени \(t\) существовал цвет, который принадлежит ровно одному отрезку, содержащему \(t\).
Примечание
Мы можем представить отрезок наблюдения каждого воина в виде отрезка по оси X;
В 1 наборе входных данных отрезки могут быть окрашены, как показано ниже (отрезки покрашены в выбранный цвет; области закрашены цветом, если данный цвет встречается в этот момент времени ровно один раз):
Во 2 наборе входных данных отрезки могут быть окрашены, как показано ниже:
В 3 наборе входных данных интервалы могут быть окрашены, как показано ниже:
