题目描述

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

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

解题思路

1. IP ↔ 整数

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

   • 转换公式：

     x = A×2^24 + B×2^16 + C×2^8 + D
     

     其中 IP 为 “A.B.C.D”。

2. 排序

   • 对所有区间按“起始整数”升序排序；若起始相同，则按“结束整数”升序。

3. 线性合并

   • 准备一个空列表 merged。
   • 依次遍历排序后的每个区间 [cur_start, cur_end]：
     1. 如果 merged 为空，直接将当前区间加入；
     2. 否则取 last = merged[最后一个]：
        • 若 cur_start > last.end + 1，说明二者既不重叠也不相邻——将 [cur_start, cur_end] 追加到 merged；
        • 否则，说明有重叠或相邻——更新 last.end = max(last.end, cur_end)。

4. 结果输出

   • 遍历 merged 中的每个整型区间，转换回 “A.B.C.D” 格式，按 [start_ip,end_ip] 打印，中间用空格或换行分隔。

完整代码

cpp

#include <bits/stdc++.h>
using namespace std;

// 将IPv4地址转换为整数，使用 long long 类型以避免溢出
long long ip_to_int(const string &ip) {
    long long a, b, c, d;
    char dot;
    istringstream iss(ip);
    iss >> a >> dot >> b >> dot >> c >> dot >> d;
    return (a << 24) | (b << 16) | (c << 8) | d;
}

// 将整数转换回IPv4地址格式
string int_to_ip(long long x) {
    return to_string((x >> 24) & 0xFF) + "." +
           to_string((x >> 16) & 0xFF) + "." +
           to_string((x >> 8)  & 0xFF) + "." +
           to_string(x & 0xFF);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    if (!(cin >> N)) return 0;
    vector<pair<long long, long long>> intervals;
    intervals.reserve(N);

    string token;
    for (int i = 0; i < N; ++i) {
        cin >> token;  // 格式: [start_ip,end_ip]
        token = token.substr(1, token.size() - 2);
        size_t comma = token.find(',');
        string start_ip = token.substr(0, comma);
        string end_ip   = token.substr(comma + 1);
        long long s = ip_to_int(start_ip);
        long long e = ip_to_int(end_ip);
        intervals.emplace_back(s, e);
    }

    // 按起始IP排序
    sort(intervals.begin(), intervals.end());

    // 合并重叠或连续的区间
    vector<pair<long long, long long>> merged;
    for (auto &iv : intervals) {
        if (merged.empty() || iv.first > merged.back().second + 1) {
            merged.push_back(iv);
        } else {
            merged.back().second = max(merged.back().second, iv.second);
        }
    }

    // 输出结果，格式 [start_ip,end_ip] 空格分隔
    for (size_t i = 0; i < merged.size(); ++i) {
        cout << "[" << int_to_ip(merged[i].first)
             << "," << int_to_ip(merged[i].second) << "]";
        if (i + 1 < merged.size()) cout << ' ';
    }

    return 0;
}

python

import sys

def ip_to_int(ip: str) -> int:
    """
    将IPv4地址从点分十进制格式转换为整数
    """
    a, b, c, d = map(int, ip.split('.'))
    return (a << 24) | (b << 16) | (c << 8) | d


def int_to_ip(num: int) -> str:
    """
    将整数转换回点分十进制格式的IPv4地址
    """
    return '.'.join(str((num >> (8 * i)) & 255) for i in range(3, -1, -1))


def merge_ip_intervals(intervals):
    """
    合并重叠和连续的IP地址区间

    参数:
        intervals: List of tuples [(start_int, end_int), ...]
    返回:
        merged: List of merged intervals as tuples
    """
    # 按起始地址排序
    intervals.sort(key=lambda x: x[0])
    merged = []

    for start, end in intervals:
        if not merged:
            merged.append([start, end])
        else:
            prev_start, prev_end = merged[-1]
            # 如果有重叠或连续（prev_end + 1 >= start）
            if start <= prev_end + 1:
                merged[-1][1] = max(prev_end, end)
            else:
                merged.append([start, end])

    return merged


def main():
    data = sys.stdin.read().strip().split()  # 读取输入并按空白分割
    n = int(data[0])
    raw_intervals = data[1:1+n]

    intervals = []
    for item in raw_intervals:
        # 去掉方括号和逗号，分割开始和结束IP
        item = item.strip()
        # 格式如 [192.168.1.1,192.168.1.3]
        start_ip, end_ip = item.strip('[]').split(',')
        start_int = ip_to_int(start_ip)
        end_int = ip_to_int(end_ip)
        intervals.append((start_int, end_int))

    merged = merge_ip_intervals(intervals)

    # 输出合并后的区间，格式为 [start_ip,end_ip] 并用空格分隔
    output = []
    for start_int, end_int in merged:
        output.append(f"[{int_to_ip(start_int)},{int_to_ip(end_int)}]")

    print(' '.join(output))

if __name__ == "__main__":
    main()

java

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.*;

public class Main {
    // 将 IPv4 地址转换为 32 位整数并返回 long
    private static long ipToLong(String ip) {
        String[] parts = ip.split("\\.");
        long A = Long.parseLong(parts[0]);
        long B = Long.parseLong(parts[1]);
        long C = Long.parseLong(parts[2]);
        long D = Long.parseLong(parts[3]);
        return (A << 24) | (B << 16) | (C << 8) | D;
    }

    // 将 long 整数转换回 IPv4 字符串
    private static String longToIp(long x) {
        long A = (x >> 24) & 0xFF;
        long B = (x >> 16) & 0xFF;
        long C = (x >> 8)  & 0xFF;
        long D = x & 0xFF;
        return A + "." + B + "." + C + "." + D;
    }

    // 合并重叠或相邻的区间
    private static List<long[]> mergeIntervals(List<long[]> intervals) {
        // 按 start 升序排序
        intervals.sort(Comparator.comparingLong(a -> a[0]));

        List<long[]> merged = new ArrayList<>();
        for (long[] iv : intervals) {
            if (merged.isEmpty() || iv[0] > merged.get(merged.size() - 1)[1] + 1) {
                // 不重叠也不相邻，添加新区间
                merged.add(new long[]{ iv[0], iv[1] });
            } else {
                // 重叠或相邻，则扩展末端
                long[] last = merged.get(merged.size() - 1);
                last[1] = Math.max(last[1], iv[1]);
            }
        }
        return merged;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // 读取区间个数
        int N = Integer.parseInt(br.readLine().trim());

        List<long[]> intervals = new ArrayList<>(N);
        for (int i = 0; i < N; i++) {
            String line = br.readLine().trim();
            // 期望格式如 "[192.168.1.1,192.168.1.3]"
            line = line.substring(1, line.length() - 1);
            String[] parts = line.split(",");
            String sIp = parts[0];
            String eIp = parts[1];
            long s = ipToLong(sIp);
            long e = ipToLong(eIp);
            intervals.add(new long[]{ s, e });
        }

        // 合并
        List<long[]> merged = mergeIntervals(intervals);

        // 输出
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < merged.size(); i++) {
            long[] iv = merged.get(i);
            sb.append("[")
              .append(longToIp(iv[0]))
              .append(",")
              .append(longToIp(iv[1]))
              .append("]");
            if (i + 1 < merged.size()) {
                sb.append(" ");
            }
        }
        System.out.println(sb.toString());
    }
}

题目内容

给定多个 $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]$