【2024年华为OD机试】 (B卷,200分)- 区间交集（Java & JS & Python&C/C++）

🕗 发布于 2025-01-19 16:47 华为od java javascript c语言 python

在这里插入图片描述

一、问题描述

题目解析

问题描述

给定一组闭区间，其中部分区间存在交集。要求：

求出任意两个区间的交集（称为公共区间）。
如果公共区间之间存在交集，则需要合并这些公共区间。
最终按升序排列输出合并后的区间列表。

如果没有任何公共区间，则输出 None。

输入描述

第一行：区间数量 N，范围为 0 <= N <= 1000。
接下来 N 行：每行表示一个区间 [start, end]，区间元素范围为 -10000 <= X <= 10000。

输出描述

按升序排列的合并后的区间列表，每个区间用空格分隔。如果没有公共区间，则输出 None。

用例

输入：
```
4
0 3
1 3
3 5
3 6
```
输出：
```
1 5
```
说明：
- 公共区间为 [1,3]、[3,3]、[3,5]。
- 这些公共区间存在交集，合并后为 [1,5]。
输入：
```
4
0 3
1 4
4 7
5 8
```
输出：
```
1 3
4 4
5 7
```
说明：
- 公共区间为 [1,3]、[4,4]、[5,7]。
- 这些公共区间不存在交集，无需合并。
输入：
```
2
1 2
3 4
```
输出：
```
None
```
说明：
- 区间 [1,2] 和 [3,4] 无交集，因此没有公共区间。

解题思路

1. 求任意两个区间的交集

对于任意两个区间 [s1, e1] 和 [s2, e2]，假设 s1 <= s2。
如果 e1 >= s2，则两个区间存在交集。
交集的左边界为 max(s1, s2)，右边界为 min(e1, e2)。
如果 e1 < s2，则两个区间无交集。

2. 收集所有公共区间

遍历所有区间的两两组合，求出它们的交集。
将所有非空的交集保存到一个列表中。

3. 合并公共区间

对公共区间列表按左边界升序排序。
使用合并区间的算法：
- 初始化一个结果列表，将第一个区间加入结果列表。
- 遍历剩余的区间，如果当前区间与结果列表中的最后一个区间有交集，则合并它们；否则，将当前区间加入结果列表。

4. 输出结果

如果合并后的区间列表为空，则输出 None。
否则，按升序输出合并后的区间列表。

实现步骤

输入处理：
- 读取区间数量 N。
- 读取 N 个区间，并存储到一个列表中。
求公共区间：
- 使用双重循环遍历所有区间的两两组合，求出它们的交集。
- 将非空的交集保存到一个新的列表中。
合并公共区间：
- 对公共区间列表按左边界升序排序。
- 使用合并区间的算法，将重叠的区间合并。
输出结果：
- 如果合并后的区间列表为空，输出 None。
- 否则，按升序输出合并后的区间列表。

复杂度分析

求公共区间：
- 时间复杂度：O(N^2)，其中 N 是区间数量。
- 空间复杂度：O(M)，其中 M 是公共区间的数量。
合并公共区间：
- 时间复杂度：O(M log M)，其中 M 是公共区间的数量（排序的复杂度）。
- 空间复杂度：O(M)，用于存储合并后的区间列表。

示例代码逻辑

以下是伪代码描述，帮助理解实现逻辑：

# 输入处理
N = 读取区间数量
intervals = []
for i in range(N):
    start, end = 读取区间
    intervals.append([start, end])

# 求公共区间
common_intervals = []
for i in range(N):
    for j in range(i + 1, N):
        s1, e1 = intervals[i]
        s2, e2 = intervals[j]
        if e1 >= s2 and e2 >= s1:  # 存在交集
            common_start = max(s1, s2)
            common_end = min(e1, e2)
            common_intervals.append([common_start, common_end])

# 合并公共区间
if not common_intervals:
    输出 None
else:
    common_intervals.sort()  # 按左边界升序排序
    merged = []
    for interval in common_intervals:
        if not merged or merged[-1][1] < interval[0]:  # 无交集
            merged.append(interval)
        else:  # 有交集，合并
            merged[-1][1] = max(merged[-1][1], interval[1])
    
    # 输出结果
    for interval in merged:
        输出 interval[0], interval[1]

总结

本题的核心在于：

如何高效地求出任意两个区间的交集。
如何合并重叠的公共区间。
通过排序和合并区间的算法，可以高效地解决这个问题。

二、JavaScript算法源码

它接收多个区间，并输出所有交集区间。我们一起来分析代码的每一部分。

代码解析

1. 输入部分：读取多行输入

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines = [];
let n;
rl.on("line", (line) => {
  lines.push(line);

  if (lines.length === 1) {
    n = parseInt(lines[0]);

    if (n == 0) {
      console.log("None");
      lines.length = 0;
    }
  }

  if (n && lines.length === n + 1) {
    lines.shift();
    const ranges = lines.map((line) => line.split(" ").map(Number));

    getResult(ranges);

    lines.length = 0;
  }
});

readline.createInterface 用来读取标准输入（stdin）中的数据。lines 数组用来保存输入的所有行。
每当用户输入一行数据时，"line" 事件被触发。我们将每一行存入 lines 数组。
当第一行输入完后（即 lines.length === 1），我们解析该行数据来获取区间的数量 n。
- 如果 n == 0，则直接输出 "None" 并退出。
- 当读取到所有区间后（即 lines.length === n + 1），我们将区间数据提取出来，并将其传递给 getResult 函数进行处理。

2. `getResult` 函数：计算交集

function getResult(ranges) {
  // 区间按照开始位置升序
  ranges.sort((a, b) => a[0] - b[0]);

  // combine用于保存交集
  const combine = [];

  // 公共区间求解
  for (let i = 0; i < ranges.length; i++) {
    const [s1, e1] = ranges[i];
    for (let j = i + 1; j < ranges.length; j++) {
      const [s2, e2] = ranges[j];
      if (s2 <= e1) {
        combine.push([s2, Math.min(e1, e2)]);
      } else {
        // 由于ranges已经升序，因此如果ranges[i]和ranges[j]没有交集的话，则也不可能和ranges[j+1]区间有交集
        break;
      }
    }
  }

  if (combine.length == 0) return console.log("None");

  // 合并公共区间
  combine.sort((a, b) => (a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]));

  let pre = combine[0];
  for (let i = 1; i < combine.length; i++) {
    const cur = combine[i];

    if (pre[1] >= cur[0]) {
      pre[1] = Math.max(cur[1], pre[1]);
    } else {
      console.log(pre.join(" "));
      pre = cur;
    }
  }

  console.log(pre.join(" "));
}

2.1 区间排序

ranges.sort((a, b) => a[0] - b[0]);

对区间数组进行排序，排序规则是按每个区间的开始位置升序排列。

2.2 计算交集

const combine = [];

for (let i = 0; i < ranges.length; i++) {
  const [s1, e1] = ranges[i];
  for (let j = i + 1; j < ranges.length; j++) {
    const [s2, e2] = ranges[j];
    if (s2 <= e1) {
      combine.push([s2, Math.min(e1, e2)]);
    } else {
      // 由于ranges已经升序，因此如果ranges[i]和ranges[j]没有交集的话，则也不可能和ranges[j+1]区间有交集
      break;
    }
  }
}

我们通过两层循环来查找所有区间的交集。
- ranges[i] 和 ranges[j] 为两个区间，如果它们有交集（即 s2 <= e1），就计算它们的交集并加入 combine 数组。
- 如果两个区间没有交集，内层循环 break，因为 ranges 数组已经按开始位置升序排列，后续的区间与当前区间也不会有交集。

2.3 没有交集时的处理

if (combine.length == 0) return console.log("None");

如果 combine 数组为空，说明没有交集，输出 "None" 并结束函数。

2.4 合并交集区间

combine.sort((a, b) => (a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]));

let pre = combine[0];
for (let i = 1; i < combine.length; i++) {
  const cur = combine[i];

  if (pre[1] >= cur[0]) {
    pre[1] = Math.max(cur[1], pre[1]);
  } else {
    console.log(pre.join(" "));
    pre = cur;
  }
}

console.log(pre.join(" "));

对 combine 数组中的区间按照开始位置升序、结束位置降序进行排序。
然后遍历所有的交集区间，尝试合并重叠的区间：
- 如果当前区间的结束位置 pre[1] 大于等于下一个区间的开始位置 cur[0]，则说明这两个区间可以合并，更新结束位置为 Math.max(pre[1], cur[1])。
- 如果当前区间不能与下一个区间合并，则输出当前区间的结果，并将 pre 更新为当前区间。

代码的关键点

区间排序：将区间按开始位置升序排列是求交集的前提。
交集计算：通过双重循环遍历区间，找到交集区间。
合并交集区间：合并所有重叠的交集区间。

时间复杂度分析

排序：ranges.sort 的时间复杂度是 O(n log n)，其中 n 是区间数量。
计算交集：两层循环计算交集的时间复杂度是 O(n^2)。
合并区间：合并区间的时间复杂度是 O(m log m)，其中 m 是交集区间的数量。

因此，总的时间复杂度是 O(n^2)。

示例

输入：

输出：

2 3
7 8

解释：

排序后的区间：(1, 3), (2, 5), (6, 8), (7, 9)
交集区间：
- (1, 3) 和 (2, 5) 交集为 (2, 3)
- (6, 8) 和 (7, 9) 交集为 (7, 8)
合并后的交集区间：(2, 3) 和 (7, 8)。

总结

这段 JavaScript 代码实现了通过交集计算和合并区间来解决问题。通过排序、计算交集、合并交集等步骤，确保正确输出交集的结果。

三、Java算法源码

这段 Java 代码的目标是解决一个区间交集问题，给定一组区间，找出其中所有的交集并将其合并。让我们逐步分析和讲解代码的具体实现。

代码讲解

1. 输入部分

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();  // 读取区间的数量
int[][] ranges = new int[n][2];  // 创建一个二维数组来保存区间
for (int i = 0; i < n; i++) {
  ranges[i][0] = sc.nextInt();  // 读取区间的开始位置
  ranges[i][1] = sc.nextInt();  // 读取区间的结束位置
}

首先，读取区间的数量 n，并创建一个二维数组 ranges 来保存每个区间的开始和结束位置。
然后通过循环读取每个区间的起始和结束值，并存储在 ranges 数组中。

2. `getResult` 函数

public static void getResult(int n, int[][] ranges) {
  // 区间按照开始位置升序
  Arrays.sort(ranges, (a, b) -> a[0] - b[0]);

对区间进行排序：使用 Arrays.sort 对 ranges 数组按每个区间的起始位置进行升序排序。
排序的比较器 (a, b) -> a[0] - b[0] 表示比较区间的第一个元素（即区间的起始位置）。

3. 计算区间交集

ArrayList<int[]> combine = new ArrayList<>();
for (int i = 0; i < n; i++) {
  int s1 = ranges[i][0], e1 = ranges[i][1];
  for (int j = i + 1; j < n; j++) {
    int s2 = ranges[j][0], e2 = ranges[j][1];
    if (s2 <= e1) {
      combine.add(new int[] {s2, Math.min(e1, e2)});
    } else {
      // 由于ranges已经升序，因此如果ranges[i]和ranges[j]没有交集的话，则也不可能和ranges[j+1]区间有交集
      break;
    }
  }
}

区间交集计算：
- 通过双重循环遍历所有区间，计算任意两个区间的交集。
- 对于每一对区间 ranges[i] 和 ranges[j]（其中 i < j），如果区间 ranges[i] 的结束位置 e1 大于等于区间 ranges[j] 的开始位置 s2，则认为这两个区间有交集。交集区间的开始位置是 s2，结束位置是 Math.min(e1, e2)。
- 将交集的区间添加到 combine 列表中。
- 如果没有交集（即 ranges[i] 和 ranges[j] 不重叠），则跳出内层循环，因为由于区间已经排序，后面的区间也不可能与当前区间有交集。

4. 处理没有交集的情况

if (combine.size() == 0) {
  System.out.println("None");
  return;
}

如果没有找到任何交集区间（即 combine 列表为空），输出 "None"。

5. 合并交集区间

combine.sort((a, b) -> a[0] != b[0] ? a[0] - b[0] : b[1] - a[1]);

int[] pre = combine.get(0);
for (int i = 1; i < combine.size(); i++) {
  int[] cur = combine.get(i);
  if (pre[1] >= cur[0]) {
    pre[1] = Math.max(cur[1], pre[1]);
  } else {
    System.out.println(pre[0] + " " + pre[1]);
    pre = cur;
  }
}

System.out.println(pre[0] + " " + pre[1]);

合并交集区间：
- 首先，对交集区间 combine 进行排序，排序规则是：按开始位置升序，如果开始位置相同，则按结束位置降序。
- 然后，遍历已排序的交集区间，合并相邻的交集区间：
  - 如果当前区间的开始位置 cur[0] 小于或等于前一个区间的结束位置 pre[1]，则两个区间有重叠或相邻，可以合并，更新前一个区间的结束位置为 Math.max(pre[1], cur[1])。
  - 否则，输出前一个区间的合并结果，并将当前区间设为新的前一个区间 pre。
最后，输出最后一个合并后的区间。

时间复杂度分析

排序的时间复杂度是 O(n log n)，其中 n 是区间的数量。
双重循环计算交集的时间复杂度是 O(n^2)，因为对于每一对区间都需要检查是否有交集。
合并交集的时间复杂度是 O(m log m)，其中 m 是交集区间的数量。
因此，整体时间复杂度为 O(n^2 + m log m)。

示例

输入：

输出：

2 3
7 8

解释：

排序后的区间：(1, 3), (2, 5), (6, 8), (7, 9)
交集区间：
- (1, 3) 和 (2, 5) 交集为 (2, 3)
- (6, 8) 和 (7, 9) 交集为 (7, 8)
合并后的交集区间：(2, 3) 和 (7, 8)。

总结

这段代码主要实现了从给定的一组区间中找出所有交集区间并合并的功能。通过排序、双重循环计算交集和合并区间，能够有效处理区间交集的问题。

四、Python算法源码

这段 Python 代码实现了一个类似之前描述的区间交集问题，目的在于找到多个区间的交集并将其合并。接下来，让我们逐步分析代码的实现过程。

代码分析

1. 输入获取

n = int(input())  # 读取区间数量
ranges = [list(map(int, input().split())) for _ in range(n)]  # 读取所有区间

通过 input() 获取输入数据。第一行是区间的数量 n。
ranges 列表保存所有的区间，每个区间是由一对整数（开始位置和结束位置）组成的列表。
使用 list(map(int, input().split())) 逐行读取每个区间的起始和结束值，将它们存入 ranges 中。

2. `getResult()` 函数：计算交集并合并

def getResult():
    ranges.sort(key=lambda x: x[0])  # 按照每个区间的起始位置升序排序

    combine = []  # 用来保存所有交集区间

    for i in range(n):
        s1, e1 = ranges[i]
        for j in range(i + 1, n):
            s2, e2 = ranges[j]
            if s2 <= e1:
                combine.append([s2, min(e1, e2)])  # 计算交集并添加到combine
            else:
                # 如果没有交集，则跳出内层循环，因为后续的区间也不可能与当前区间有交集
                break

排序：首先，按照每个区间的起始位置升序对 ranges 进行排序。这是为了确保交集的计算可以按顺序进行。
计算交集：使用双层循环遍历所有区间对（ranges[i] 和 ranges[j]，其中 i < j），如果两个区间 ranges[i] 和 ranges[j] 有交集（即 s2 <= e1），则计算它们的交集区间 [s2, min(e1, e2)]，并将交集加入 combine 列表。
- 注意，如果没有交集（即 s2 > e1），则跳出内层循环，因为根据已排序的区间，后面的区间与当前区间也不会有交集。

3. 没有交集的处理

if len(combine) == 0:
    print("None")
    return

如果 combine 为空，说明没有找到任何交集区间，则输出 "None" 并退出函数。

4. 合并交集区间

combine.sort(key=lambda x: (x[0], -x[1]))  # 先按开始位置升序排序，如果开始位置相同，则按结束位置降序排序

pre = combine[0]  # 初始化合并的第一个区间
for i in range(1, len(combine)):
    cur = combine[i]

    if pre[1] >= cur[0]:  # 如果当前区间与前一个区间有交集或相邻
        pre[1] = max(cur[1], pre[1])  # 合并区间，更新结束位置
    else:
        print(" ".join(map(str, pre)))  # 输出前一个区间
        pre = cur  # 更新前一个区间为当前区间

print(" ".join(map(str, pre)))  # 最后输出最后一个区间

合并区间：通过对交集区间 combine 按照开始位置升序排序，并在开始位置相同的情况下按结束位置降序排序，确保合并的顺序正确。
合并过程：遍历所有交集区间，检查当前区间 cur 是否与前一个区间 pre 有重叠或相邻（即 pre[1] >= cur[0]）。如果有重叠，更新前一个区间的结束位置为 max(pre[1], cur[1])，否则输出前一个区间并更新 pre 为当前区间。
最后输出最后一个区间 pre。

代码的整体逻辑

输入读取：先读取区间数量，再读取所有区间的起始和结束值。
交集计算：通过排序和两层循环计算所有区间对之间的交集。
合并交集区间：合并所有交集区间，并输出结果。如果没有交集区间，输出 "None"。

时间复杂度分析

排序：ranges.sort() 的时间复杂度是 O(n log n)，其中 n 是区间数量。
交集计算：双层循环遍历所有区间对，计算交集的时间复杂度是 O(n^2)。
合并区间：合并区间的时间复杂度是 O(m log m)，其中 m 是交集区间的数量，m <= n。

因此，整体时间复杂度为 O(n^2)，这是因为计算交集的部分是最耗时的。

示例

输入：

输出：

2 3
7 8

解释：

排序后的区间：(1, 3), (2, 5), (6, 8), (7, 9)
交集区间：
- (1, 3) 和 (2, 5) 交集为 (2, 3)
- (6, 8) 和 (7, 9) 交集为 (7, 8)
合并后的交集区间：(2, 3) 和 (7, 8)。

总结

这段 Python 代码有效地解决了区间交集和合并的问题。通过排序、计算交集以及合并区间，能够正确地输出所有交集区间。如果没有交集，程序会输出 "None"。

五、C/C++算法源码：

好的，下面我将根据你的要求将该 Python 代码转换为 C++ 和 C 语言版本，并进行详细的中文注释和讲解。

C++ 代码实现

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void getResult(vector<pair<int, int>>& ranges, int n) {
    // 区间按照开始位置升序排序
    sort(ranges.begin(), ranges.end());

    // combine用于保存公共区间
    vector<pair<int, int>> combine;

    // 计算所有区间的交集
    for (int i = 0; i < n; i++) {
        int s1 = ranges[i].first, e1 = ranges[i].second;
        for (int j = i + 1; j < n; j++) {
            int s2 = ranges[j].first, e2 = ranges[j].second;
            if (s2 <= e1) {
                combine.push_back({s2, min(e1, e2)});  // 计算交集
            } else {
                break;  // 没有交集，跳出内层循环
            }
        }
    }

    // 如果没有找到任何交集区间，输出"None"
    if (combine.empty()) {
        cout << "None" << endl;
        return;
    }

    // 合并交集区间
    sort(combine.begin(), combine.end(), [](pair<int, int>& a, pair<int, int>& b) {
        return a.first == b.first ? a.second > b.second : a.first < b.first;
    });

    pair<int, int> pre = combine[0];  // 初始化第一个区间
    for (int i = 1; i < combine.size(); i++) {
        pair<int, int> cur = combine[i];

        // 如果当前区间与前一个区间有交集或相邻
        if (pre.second >= cur.first) {
            pre.second = max(cur.second, pre.second);  // 合并区间
        } else {
            // 输出合并后的区间
            cout << pre.first << " " << pre.second << endl;
            pre = cur;  // 更新前一个区间
        }
    }
    
    // 最后输出最后一个区间
    cout << pre.first << " " << pre.second << endl;
}

int main() {
    int n;
    cin >> n;  // 输入区间的数量
    vector<pair<int, int>> ranges(n);  // 创建一个pair数组来保存区间
    for (int i = 0; i < n; i++) {
        cin >> ranges[i].first >> ranges[i].second;  // 输入每个区间的起始和结束
    }

    // 调用计算交集并合并的函数
    getResult(ranges, n);

    return 0;
}

C++ 代码讲解

输入部分：
```
int n;
cin >> n;
vector<pair<int, int>> ranges(n);
for (int i = 0; i < n; i++) {
    cin >> ranges[i].first >> ranges[i].second;
}
```
- 首先，我们读取区间的数量 n。
- 使用 vector<pair<int, int>> 存储每个区间的起始和结束值。pair<int, int> 是一个存储两个整数的容器。
- 接着读取每个区间的起始和结束值并存入 ranges 中。
排序部分：
```
sort(ranges.begin(), ranges.end());
```
- 使用 std::sort 对 ranges 进行排序，排序依据是区间的起始位置（ranges[i].first）。因为 std::sort 默认是升序排序，所以我们无需额外指定排序规则。

计算交集：

for (int i = 0; i < n; i++) {
    int s1 = ranges[i].first, e1 = ranges[i].second;
    for (int j = i + 1; j < n; j++) {
        int s2 = ranges[j].first, e2 = ranges[j].second;
        if (s2 <= e1) {
            combine.push_back({s2, min(e1, e2)});
        } else {
            break;
        }
    }
}

通过双层循环遍历每一对区间 ranges[i] 和 ranges[j]，其中 i < j。判断是否有交集（即 s2 <= e1），如果有交集，计算交集并将其加入 combine。

没有交集时输出 “None”：

if (combine.empty()) {
    cout << "None" << endl;
    return;
}

合并交集区间：

sort(combine.begin(), combine.end(), [](pair<int, int>& a, pair<int, int>& b) {
    return a.first == b.first ? a.second > b.second : a.first < b.first;
});

pair<int, int> pre = combine[0];
for (int i = 1; i < combine.size(); i++) {
    pair<int, int> cur = combine[i];
    if (pre.second >= cur.first) {
        pre.second = max(cur.second, pre.second);
    } else {
        cout << pre.first << " " << pre.second << endl;
        pre = cur;
    }
}

cout << pre.first << " " << pre.second << endl;

首先对交集区间 combine 进行排序。排序规则是：首先按开始位置升序，如果开始位置相同，则按结束位置降序排序。
遍历所有交集区间，尝试合并相邻的交集区间。如果可以合并，就更新结束位置，否则输出当前区间，并将当前区间设为新的前一个区间。

主函数：

int main() {
    int n;
    cin >> n;
    vector<pair<int, int>> ranges(n);
    for (int i = 0; i < n; i++) {
        cin >> ranges[i].first >> ranges[i].second;
    }
    getResult(ranges, n);
    return 0;
}

main() 函数中首先读取区间数量 n，然后读取区间数据，最后调用 getResult() 进行交集计算和合并。

C 代码实现

#include <stdio.h>
#include <stdlib.h>

// 定义结构体表示区间
typedef struct {
    int start;  // 区间的起始位置
    int end;    // 区间的结束位置
} Interval;

// 比较函数，用于排序区间
int compare(const void* a, const void* b) {
    Interval* intervalA = (Interval*)a;
    Interval* intervalB = (Interval*)b;

    // 如果起始位置相同，按结束位置降序排序
    if (intervalA->start == intervalB->start) {
        return intervalB->end - intervalA->end;
    }
    // 按起始位置升序排序
    return intervalA->start - intervalB->start;
}

// 算法入口，计算交集并合并区间
void getResult(Interval* ranges, int n) {
    // 对区间按起始位置升序排序，如果起始位置相同，则按结束位置降序排序
    qsort(ranges, n, sizeof(Interval), compare);

    // 用来保存交集区间
    Interval* combine = (Interval*)malloc(n * sizeof(Interval));
    int combineSize = 0;  // 交集区间数量

    // 计算所有区间的交集
    for (int i = 0; i < n; i++) {
        int s1 = ranges[i].start, e1 = ranges[i].end;
        for (int j = i + 1; j < n; j++) {
            int s2 = ranges[j].start, e2 = ranges[j].end;
            // 判断区间是否有交集
            if (s2 <= e1) {
                // 计算交集区间
                combine[combineSize].start = s2;
                combine[combineSize].end = (e1 < e2) ? e1 : e2;
                combineSize++;
            } else {
                break;  // 后续区间与当前区间无交集，提前结束内层循环
            }
        }
    }

    // 如果没有交集区间，输出"None"
    if (combineSize == 0) {
        printf("None\n");
        free(combine);
        return;
    }

    // 对交集区间按照起始位置升序排序，如果起始位置相同，则按结束位置降序排序
    qsort(combine, combineSize, sizeof(Interval), compare);

    // 合并交集区间
    Interval pre = combine[0];  // 初始化第一个区间
    for (int i = 1; i < combineSize; i++) {
        Interval cur = combine[i];
        // 判断当前区间和前一个区间是否有交集
        if (pre.end >= cur.start) {
            // 如果有交集，更新前一个区间的结束位置
            pre.end = (pre.end > cur.end) ? pre.end : cur.end;
        } else {
            // 如果没有交集，输出前一个区间
            printf("%d %d\n", pre.start, pre.end);
            pre = cur;  // 更新前一个区间为当前区间
        }
    }
    // 最后输出最后一个区间
    printf("%d %d\n", pre.start, pre.end);

    // 释放内存
    free(combine);
}

int main() {
    int n;
    scanf("%d", &n);  // 读取区间数量

    // 动态分配内存来存储区间
    Interval* ranges = (Interval*)malloc(n * sizeof(Interval)); 

    // 读取每个区间的起始和结束位置
    for (int i = 0; i < n; i++) {
        scanf("%d %d", &ranges[i].start, &ranges[i].end);
    }

    // 调用算法函数，计算交集并合并
    getResult(ranges, n);

    // 释放动态分配的内存
    free(ranges);

    return 0;
}

C 代码讲解

1. 输入部分

scanf("%d", &n);  // 读取区间数量
Interval* ranges = (Interval*)malloc(n * sizeof(Interval));  // 动态分配内存存储区间
for (int i = 0; i < n; i++) {
    scanf("%d %d", &ranges[i].start, &ranges[i].end);  // 读取每个区间的起始和结束值
}

scanf 用于读取输入数据。首先读取区间的数量 n。
使用 malloc 动态分配内存来存储 n 个 Interval 结构体，每个结构体存储一个区间的起始和结束位置。
然后通过 scanf 循环读取每个区间的起始和结束值。

2. 排序部分

qsort(ranges, n, sizeof(Interval), compare);

qsort 是 C 标准库中的快速排序函数，用来对区间 ranges 按照区间的起始位置升序排序。如果起始位置相同，则按结束位置降序排序。排序规则通过 compare 函数实现。

3. 计算交集

for (int i = 0; i < n; i++) {
    int s1 = ranges[i].start, e1 = ranges[i].end;
    for (int j = i + 1; j < n; j++) {
        int s2 = ranges[j].start, e2 = ranges[j].end;
        if (s2 <= e1) {
            combine[combineSize].start = s2;
            combine[combineSize].end = (e1 < e2) ? e1 : e2;
            combineSize++;
        } else {
            break;
        }
    }
}

双重循环遍历所有区间对 (ranges[i], ranges[j])，其中 i < j。对于每一对区间，判断它们是否有交集（即 s2 <= e1），如果有交集，则将交集区间计算出来并保存到 combine 数组中。
如果没有交集（即 s2 > e1），则跳出内层循环，因为根据已排序的区间，后续的区间与当前区间也不会有交集。

4. 没有交集时输出 "None"

if (combineSize == 0) {
    printf("None\n");
    free(combine);
    return;
}

如果没有找到任何交集区间，输出 "None"，并释放 combine 数组的内存，然后结束函数。

5. 合并交集区间

qsort(combine, combineSize, sizeof(Interval), compare);

对 combine 数组中的交集区间进行排序。排序规则同样是按起始位置升序，如果起始位置相同，则按结束位置降序。

Interval pre = combine[0];
for (int i = 1; i < combineSize; i++) {
    Interval cur = combine[i];
    if (pre.end >= cur.start) {
        pre.end = (pre.end > cur.end) ? pre.end : cur.end;
    } else {
        printf("%d %d\n", pre.start, pre.end);
        pre = cur;
    }
}
printf("%d %d\n", pre.start, pre.end);

通过遍历所有交集区间，尝试合并相邻或重叠的区间。
- 如果当前区间 cur 和前一个区间 pre 有交集（即 pre.end >= cur.start），则更新前一个区间的结束位置为 max(pre.end, cur.end)。
- 如果当前区间和前一个区间没有交集，输出当前的前一个区间，并更新 pre 为当前区间。
最后输出最后一个合并后的区间。

6. 释放内存

free(ranges);  // 释放存储区间的内存

在 main 函数结束时，释放动态分配的内存，避免内存泄漏。

总结

这段 C 代码实现了与 C++ 代码类似的功能：读取多个区间，计算它们的交集并合并交集区间。如果没有交集，输出 "None"；否则输出合并后的交集区间。
qsort 用于排序区间，而通过双重循环计算交集并合并区间。

这两种语言的实现方法相似，主要区别在于内存管理方面（C++ 使用 std::vector，而 C 语言使用 malloc 动态分配内存），以及排序函数的实现方式（C++ 使用 std::sort，而 C 使用 qsort）。

六、尾言

什么是华为OD？

华为OD（Outsourcing Developer，外包开发工程师）是华为针对软件开发工程师岗位的一种招聘形式，主要包括笔试、技术面试以及综合面试等环节。尤其在笔试部分，算法题的机试至关重要。

为什么刷题很重要？

机试是进入技术面的第一关：
华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。
技术面试需要手撕代码：
技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。
入职后的可信考试：
入职华为后，还需要通过“可信考试”。可信考试分为三个等级：
- 入门级：主要考察基础算法与编程能力。
- 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
- 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

2024年8月14日之后，华为OD机试的题库转为 E卷，由往年题库（D卷、A卷、B卷、C卷）和全新题目组成。刷题时可以参考以下策略：

关注历年真题：
- 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
- 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。
适应新题目：
- E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
- 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。
掌握常见算法：
华为OD考试通常涉及以下算法和数据结构：
- 排序算法（快速排序、归并排序等）
- 动态规划（背包问题、最长公共子序列等）
- 贪心算法
- 栈、队列、链表的操作
- 图论（最短路径、最小生成树等）
- 滑动窗口、双指针算法
保持编程规范：
- 注重代码的可读性和注释的清晰度。
- 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

官方参考：
- 华为招聘官网或相关的招聘平台会有一些参考信息。
- 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。
加入刷题社区：
- 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
- 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。
寻找系统性的教程：
- 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
- 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

刷题的过程可能会比较枯燥，但它能够显著提升编程能力和算法思维。无论是为了通过华为OD的招聘考试，还是为了未来的职业发展，这些积累都会成为重要的财富。

考试注意细节

本地编写代码
- 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。
调整心态，保持冷静
- 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。
输入输出完整性
- 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。
快捷键使用
- 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
- 避免使用 Ctrl+S，以免触发浏览器的保存功能。
浏览器要求
- 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。
交卷相关
- 答题前，务必仔细查看题目示例，避免遗漏要求。
- 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
- 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。
时间和分数安排
- 总时间：150 分钟；总分：400 分。
- 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。
考试环境准备
- 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
- 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。
技术问题处理
- 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
- 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

祝你考试顺利，取得理想成绩！

原文地址：https://blog.csdn.net/m0_63168877/article/details/145213222

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：Golang Gin系列-4：Gin Framework入门教程
下一篇：Go-知识版本演进

C++中型游戏——龙虎斗 1.0.0 版本
中型游戏《龙虎斗》1.0——关卡+技能特别策划：李XX
阅读更多2025-01-19
LeetCode 2956. 找到两个数组中的公共元素
在本篇文章中，我们将探讨如何求解 LeetCode 上的 2956. 找到两个数组中的公共元素问题。这个问题要求我们找到两个数组中公共元素的出现次数，并分别计算这些公共元素在各自数组中的出现次。
阅读更多2025-01-19
关于扫雷的自动补空实现C语言
相信很多朋友在用C语言实现扫雷功能时，都想实现扫雷里面的的自动补足功能，但总是难以实现，在这里我将分享一种方法——递归思想
阅读更多2025-01-19
在线正则表达式调试工具
正则表达式测试工具
阅读更多2025-01-19
matlab的eval函数
H_var是一个包含变量名H_1296_3_4的字符串。eval会把H_var中的值当作一个变量名，查找该变量并返回它的值。：将H_1296_3_4变量的值赋给baseH。这样，baseH最终将持有与
阅读更多2025-01-19
Windows11电脑总是一闪一闪的，黑一下亮一些怎么解决
在电脑开始图片上，右键点击设备管理器。首先右键点击更新驱动程序。首先右键点击更新驱动程序。选择最新版本进行安装。选择最新版本进行安装。如果对您有帮助，请您。
阅读更多2025-01-19
React的应用级框架推荐——Next、Modern、Blitz等，快速搭建React项目
在 React 企业级应用开发中，和是三个常见的框架，它们提供了不同的特性和功能，旨在简化开发流程并提高应用的性能和扩展性。如果你需要一个成熟、社区活跃、功能丰富的通用框架，Next.js 是首选。如
阅读更多2025-01-19
乐观锁与悲观锁
一件商品，成本价是80元，售价是100元。老板先是通知小李，说你去把商品价格增加50元。小李正在玩游戏，耽搁了一个小时。正好一个小时后，老板觉得商品价格增加到150元，价格太高，可能会影响销量。又通知
阅读更多2025-01-19
C#高级：通过 Assembly 类加载 DLL 和直接引用DLL的方法大全
【代码】C#高级：通过 Assembly 类加载 DLL 并打印类的属性名称。
阅读更多2025-01-19
线性表代码实战
由n(n>=0)个相同类型的元素组成的有序集合。!!!定义、插入、删除操作一定要修改线性表长度呀！！！插入和删除操作的i操作i的合法范围插入【1，n+1】删除【1，n】//让顺序表存储其他类
阅读更多2025-01-19

【2024年华为OD机试】 (B卷,200分)- 区间交集（Java & JS & Python&C/C++）

一、问题描述

题目解析

问题描述

输入描述

输出描述

用例

解题思路

1. 求任意两个区间的交集

2. 收集所有公共区间

3. 合并公共区间

4. 输出结果

实现步骤

复杂度分析

示例代码逻辑

总结

二、JavaScript算法源码

代码解析

1. 输入部分：读取多行输入

2. getResult 函数：计算交集

2.1 区间排序

2.2 计算交集

2.3 没有交集时的处理

2.4 合并交集区间

代码的关键点

时间复杂度分析

示例

输入：

输出：

解释：

总结

三、Java算法源码

代码讲解

1. 输入部分

2. getResult 函数

3. 计算区间交集

4. 处理没有交集的情况

5. 合并交集区间

时间复杂度分析

示例

输入：

输出：

解释：

总结

四、Python算法源码

代码分析

1. 输入获取

2. getResult() 函数：计算交集并合并

3. 没有交集的处理

4. 合并交集区间

代码的整体逻辑

时间复杂度分析

示例

输入：

输出：

解释：

总结

五、C/C++算法源码：

C++ 代码实现

C++ 代码讲解

C 代码实现

C 代码讲解

1. 输入部分

2. 排序部分

3. 计算交集

4. 没有交集时输出 "None"

5. 合并交集区间

6. 释放内存

总结

六、尾言

什么是华为OD？

为什么刷题很重要？

刷题策略与说明：

如何获取资源？

积极心态与持续努力：

考试注意细节

相关文章

2. `getResult` 函数：计算交集

2. `getResult` 函数

2. `getResult()` 函数：计算交集并合并