CF809D Hitchhiking in the Baltic States

Leha 和 Noora 决定去波罗的海国家旅行。正如你在上一题中所知，Leha 在餐厅的停车场丢了车。不幸的是，向看门人询问也没有帮黑客找到车，所以朋友们决定去搭便车。 他们计划一共参观 $n$ 个城市。然而，第 $i$ 个城市的景点只在从 $l_{i}$ 到 $r_{i}$ 天对游客开放。 该怎么办呢？Leha 建议为每个城市 $i$ 选择一天作为他们参观该城市的日期，即任选一个整数 $x_{i}$，满足区间 $[l_{i}, r_{i}]$。随后，Noora 会选择一个城市的子序列 $id_{1}, id_{2}, ..., id_{k}$，要求这些子序列中的城市编号严格递增，即对所有 $1 \leq i < k$，都有 $id_{i} < id_{i+1}$，并且参观的日期也严格递增，即 $x_{id_i} < x_{id_{i+1}}$。 请你帮助 Leha 和 Noora，为每个城市 $i$ 选择一个 $x_{i}$，以及选择一个城市编号的子序列 $id_{1}, id_{2}, ..., id_{k}$，使得他们可以参观的城市数量最大。 你可以假定，Leha 和 Noora 可以从任意一天出发开始旅行。

第一行包含一个整数 $n$（$1 \leq n \leq 3 \times 10^{5}$），表示 Leha 和 Noora 计划参观的城市数量。 接下来的 $n$ 行中，每行包含两个整数 $l_{i}$，$r_{i}$（$1 \leq l_{i} \leq r_{i} \leq 10^9$），表示第 $i$ 个城市的景点在第 $l_{i}$ 天至第 $r_{i}$ 天期间对游客开放。

输出一个整数，表示 Leha 和 Noora 最多能参观的城市数量。

请考虑第一个示例。 我们可以这样安排：第二个城市在第一天访问，第三个城市在第三天访问，第五个城市在第四天访问。这将是最优答案。 由 ChatGPT 5 翻译