题目内容

你作为数据中心网络地址规划人员，需要尽可能满足不同业务的网络地址需求。每个业务需要的地址范围为一个闭区间 [start_ip,end_ip] 表示，其中 start_ip是起始 $IP$ 地址，end_ip 是终止 $IP$ 地址，end_ip 大于等于 start_ip。

不同业务的 $IP$ 地址不能重叠，因此你需要将业务地址需求，按照一定规则排序，让数据中心网络地址规划尽可能满足更多数量的业务需求。当业多数量相同时，以 $IP$ 地址占用最少优先。当业务数量和 $IP$ 地址占用数量相同时，按照 $IP$ 范围顺序，比较起始 $IP$ 地址，起始地址最小者优先。

输入描述

题解

题面描述

给定 $N$ 个业务，每个业务需要的 IP 地址范围是一个闭区间 $[start_{ip}, end_{ip}]$，其中 $start_{ip}$ 表示起始 IP，$end_{ip}$ 表示终止 IP，并且满足 $end_{ip} \geq start_{ip}$。由于不同业务的 IP 地址不能重叠，需要从这些业务中选出一些不重叠的区间，使得满足的业务数量最多。在满足业务数量最多的前提下，选出占用 IP 地址数量最少的方案；如果业务数量和 IP 地址占用数量均相同，则按照选中区间中各业务 $start_{ip}$ 的字典序排序，起始 IP 较小者优先。

输入格式：

• 第一行输入一个整数 $N$，其中 $1 \leq N \leq 1000$。
• 接下来 $N$ 行，每行输入一个 IP 区间，格式为 $start_{ip}\ end_{ip}$，其中 $start_{ip}$ 和 $end_{ip}$ 为合法的 IPv4 地址。