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