题目描述

给定多个 $IP$ 区间，其中每个区间表示为 [start_ip,end_ip]，请合并所有重叠和连续的 $IP$ 区间，并返回一个 $IP$ 区间顺序集合。

区间连续要求按照 start_ip 从小到大升序排序。

解题思路

1. IP ↔ 整数

   • 将每个 IPv4 地址转换为一个 32 位整数，便于排序和相邻判断。

题目内容

给定多个 $IP$ 区间，其中每个区间表示为 [start_ip,end_ip]，请合并所有重叠和连续的 $IP$ 区间，并返回一个 $IP$ 区间顺序集合。

区间连续要求按照 start_ip 从小到大升序排序。

输入描述

1.第一行为区间个数 $N$ ，有效范围为 $[1,100]$

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$ 个区间。每个区间的格式为 [start_ip,end_ip] , 且用空格分隔。

样例1

输入

3
[192.168.1.1,192.168.1.3]
[192.168.1.2,192.168.1.3]
[192.168.1.4,192.168.1.5]

输出

[192.168.1.1,192.168.1.5]

说明

• 区间 $[192.168.1.1,192.168.1.3]$ 和区间 $[192.168.1.2,192.168.1.3]$ 的重叠部分是 $[192.168.1.2,192.168.1.3]$。

因此可以合并为 $[192.168.1.1,192.168.1.3]$。

• 区间 $[192.168.1.1,192.168.1.3]$ 和区间 $[192.168.1.4,192.168.1.5]$ 为连续 IP 。

因此也可以合并为 $[192.168.1.1,192.168.1.5]$。

样例2

输入

3
[192.168.1.5,192.168.1.8]
[192.168.1.6,192.168.1.7]
[192.168.1.2,192.168.1.3]

输出

[192.168.1.2,192.168.1.3] [192.168.1.5,192.168.1.8]

说明

区间 $[192.168.1.5,192.168.1.8]$ 和区间 $B$ $[192.168.1.6,192.168.1.7]$ 的重叠部分是 $[192.168.1.6,192.168.1.7]$。

因此可以合并为 $[192.168.1.5,192.168.1.8]$，而区间 $C$ $[192.168.1.2,192.168.1.3]$ 与 $[192.168.1.5,192.168.1.8]$ 既不重叠，也不连续。

因此输出为 $[193.168.1.2,193.168.1.3][193.168.1.5,193.168.1.8]$