Удаление магических плиток
Айимок — волшебник.
Его ежедневная задача — выстраивать магические плитки в ряд, а затем произносить магическое заклинание.
Магические плитки и их расположение подчиняются следующим правилам:
Каждая магическая плитка имеет форму трапеции с высотой 1.
Некоторые магические плитки могут перекрываться с другими магическими плитками.
Магические плитки располагаются на 2D координатной системе.
Верхний край магических плиток лежит на горизонтальной линии, где координата y равна 1.
Нижний край магических плиток лежит на горизонтальной линии, где координата y равна 0.
После произнесения магического заклинания он должен убрать эти магические плитки. Однажды он обнаружил, что удаление большого количества магических плиток очень утомительно, поэтому решил упростить этот процесс.
Теперь он освоил "Заклинание Магнетизации", чтобы эффективно удалять магические плитки. Заклинание удаляет набор магических плиток одновременно. Любая пара двух магических плиток в наборе должна перекрываться друг с другом.
Например, в Рис. 1 он может произнести Заклинание Магнетизации на все три магические плитки, чтобы удалить их одновременно, так как они все перекрываются друг с другом. (Обратите внимание, что высоты магических плиток намеренно изменены для более легкого понимания.)
Рис. 1: Набор магических плиток, которые можно удалить одновременно
Однако, в Рис. 2 он не может произнести Заклинание Магнетизации на все три магические плитки одновременно, так как плитка 1 и плитка 3 не перекрываются.
Рис. 2: Набор магических плиток, которые нельзя удалить одновременно
Он хочет удалить все магические плитки с минимальным количеством Заклинаний Магнетизации, потому что произнесение заклинания требует много магической энергии.
Рассмотрим случай на Рис. 3. Он может удалить все магические плитки, произнеся Заклинание Магнетизации три раза; первое заклинание для плиток 1 и 2, второе заклинание для плиток 3 и 4, и третье заклинание для плиток 5 и 6.
Рис. 3: Один из способов удалить все магические плитки (НЕ минимальное количество заклинаний)
На самом деле, он может удалить все магические плитки, произнеся Заклинание Магнетизации всего дважды; первое заклинание для плиток 1, 2 и 3, второе заклинание для плиток 4, 5 и 6. И это минимальное количество необходимых заклинаний для удаления всех магических плиток.
Рис. 4: Оптимальный способ удалить все магические плитки (минимальное количество заклинаний)
Дан набор магических плиток, ваша задача — создать программу, которая выводит минимальное количество произнесений Заклинания Магнетизации, чтобы удалить все эти магические плитки.
Может быть магическая плитка, которая не перекрывается с другими плитками, однако, он все равно должен произнести Заклинание Магнетизации, чтобы удалить ее.
Входные данные
Ввод следует следующему формату:
N
xLower_11 xLower_12 xUpper_11 xUpper_12
xLower_21 xLower_22 xUpper_21 xUpper_22
xLower_31 xLower_32 xUpper_31 xUpper_32
...
xLower_N1 xLower_N2 xUpper_N1 xUpper_N2
Первая строка содержит целое число N, которое означает количество магических плиток.
Затем следуют N строк, содержащих информацию о магических плитках.
(i+1)-я строка включает четыре целых числа xLower_i1, xLower_i2, xUpper_i1 и xUpper_i2, которые означают, что угловые точки i-й магической плитки расположены в точках (xLower_i1, 0), (xLower_i2, 0), (xUpper_i1, 1) и (xUpper_i2, 1).
Можно предположить, что ни одна пара магических плиток не будет иметь общих угловых точек. То есть, все xLowerij различны, и все xUpperij также различны. Ввод следует следующим ограничениям:
1 ≤ N ≤ 10^5
1 ≤ xLower_i1 < xLower_i2 ≤ 10^9
1 ≤ xUpper_i1 < xUpper_i2 ≤ 10^9
Все xLower_ij различны.
Все xUpper_ij различны.
Выходные данные
Ваша программа должна вывести минимальное количество произнесений Заклинания Магнетизации, чтобы удалить все магические плитки.