题解

题面描述

给定 $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 地址。

题目内容

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

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

输入描述

1.第一行为业务个数 $N$ ，有效范围为 $[1,1000]$

2.输入 $N$ 行 $IP$ 地址区间，其中每个区间的格式为 start_ip end_ip (中间用空格分隔)，其中 start_ip 和 end_ip 为合法的 $IPv4$ 地址点分十进制格式，即 $A,B,C,D$ ，其中 $A、B、C$ 和 $D$ 的取值范围为 $[0,255]$ 。

3.$IP$ 地址大小的比较，是按照 $A、B、C$ 和 $D$ 的顺序进行比较。

输出描述

输出排序好的 $M$ 个 $IP$ 区间，每行一个。每个区间的格式为 start_ip end_ip , 中间用空格分隔。

样例1

输入

3
192.168.1.9 192.168.1.12
192.168.1.1 192.168.1.10
192.168.1.12 192.168.1.13

输出

192.168.1.1 192.168.1.10
192.168.1.12 192.168.1.13

说明

区间 1(192.168.1.9 192.168.1.12) 与区间 2(192.168.1.1 192.168.1.10)和 区间 3(192.168.1.12.192.168.1.13)均有重叠。

因此可规划的业务地址范围为区间 1(192.168.1.1 192.168.1.10) 和 (192.168.1.12 192.168.1.13)，其满足的业务数量最多。

样例2

输入

4
192.168.1.9 192.168.1.12
192.168.1.13 192.168.1.15
192.168.1.7 192.168.1.10
192.168.1.11 192.168.1.17

输出

192.168.1.7 192.168.1.10
192.168.1.13 192.168.1.15

说明

共有 $3$ 种方案，都是两个业务：

1. 192.168.1.7 192.168.1.10 和 192.168.1.13 192.168.1.15

2. 192.168.1.7 192.168.1.10 和 192.168.1.11 192.168.1.17

3. 192.168.1.9 192.168.1.12 和 192.168.1.13 192.168.1.15

方案 $1$ 占用 $7$ 个 $IP$ ，方案 $2$ 占用 $11$ 个 $IP$ ，方案 $3$ 占用 $7$ 个 $IP$ 。从 $IP$ 占用数量上，方案 $2$ 被放弃。

方案 $1$ 和方案 $3$ 对比，第一个业务区间，方案 $1$ 的起始 $IP$ 比方案 $3$ 的起始 $IP$ 小，因此选择方案 $1$ 。