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

server/2025/1/19 7:19:37/

在这里插入图片描述

一、问题描述

题目解析

问题描述

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

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

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

输入描述
  • 第一行：区间数量 N，范围为 0 <= N <= 1000。
  • 接下来 N 行：每行表示一个区间 [start, end]，区间元素范围为 -10000 <= X <= 10000。
输出描述
  • 按升序排列的合并后的区间列表，每个区间用空格分隔。如果没有公共区间，则输出 None。
用例

  1. 输入：

    4
0 3
1 3
3 5
3 6

    输出：

    1 5

    说明：

    • 公共区间为 [1,3]、[3,3]、[3,5]。
    • 这些公共区间存在交集，合并后为 [1,5]。

  2. 输入：

    4
0 3
1 4
4 7
5 8

    输出：

    1 3
4 4
5 7

    说明：

    • 公共区间为 [1,3]、[4,4]、[5,7]。
    • 这些公共区间不存在交集，无需合并。

  3. 输入：

    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。
  • 否则，按升序输出合并后的区间列表。

实现步骤

  1. 输入处理：

    • 读取区间数量 N。
    • 读取 N 个区间，并存储到一个列表中。

  2. 求公共区间：

    • 使用双重循环遍历所有区间的两两组合，求出它们的交集。
    • 将非空的交集保存到一个新的列表中。

  3. 合并公共区间：

    • 对公共区间列表按左边界升序排序。
    • 使用合并区间的算法，将重叠的区间合并。

  4. 输出结果：

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

复杂度分析

  1. 求公共区间：

    • 时间复杂度：O(N^2)，其中 N 是区间数量。
    • 空间复杂度：O(M)，其中 M 是公共区间的数量。

  2. 合并公共区间：

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

示例代码逻辑

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

python"># 输入处理
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]

总结

本题的核心在于：

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

二、JavaScript算法源码

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

代码解析

1. 输入部分：读取多行输入
javascript">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 函数：计算交集
javascript">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 区间排序
javascript">ranges.sort((a, b) => a[0] - b[0]);
  • 对区间数组进行排序，排序规则是按每个区间的开始位置升序排列。
2.2 计算交集
javascript">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 没有交集时的处理
javascript">if (combine.length == 0) return console.log("None");
  • 如果 combine 数组为空，说明没有交集，输出 "None" 并结束函数。
2.4 合并交集区间
javascript">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 更新为当前区间。

代码的关键点

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

时间复杂度分析

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

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

示例

输入：
4
1 3
2 5
6 8
7 9
输出：
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. 输入部分
java">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 函数
java">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. 计算区间交集
java">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. 处理没有交集的情况
java">if (combine.size() == 0) {System.out.println("None");return;
}
  • 如果没有找到任何交集区间（即 combine 列表为空），输出 "None"。
5. 合并交集区间
java">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)。

示例

输入：
4
1 3
2 5
6 8
7 9
输出：
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. 输入获取
python">n = int(input())  # 读取区间数量
ranges = [list(map(int, input().split())) for _ in range(n)]  # 读取所有区间
  • 通过 input() 获取输入数据。第一行是区间的数量 n。
  • ranges 列表保存所有的区间，每个区间是由一对整数（开始位置和结束位置）组成的列表。
  • 使用 list(map(int, input().split())) 逐行读取每个区间的起始和结束值，将它们存入 ranges 中。
2. getResult() 函数：计算交集并合并
python">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)])  # 计算交集并添加到combineelse:# 如果没有交集，则跳出内层循环，因为后续的区间也不可能与当前区间有交集break
  • 排序：首先，按照每个区间的起始位置升序对 ranges 进行排序。这是为了确保交集的计算可以按顺序进行。
  • 计算交集：使用双层循环遍历所有区间对（ranges[i] 和 ranges[j]，其中 i < j），如果两个区间 ranges[i] 和 ranges[j] 有交集（即 s2 <= e1），则计算它们的交集区间 [s2, min(e1, e2)]，并将交集加入 combine 列表。
    • 注意，如果没有交集（即 s2 > e1），则跳出内层循环，因为根据已排序的区间，后面的区间与当前区间也不会有交集。
3. 没有交集的处理
python">if len(combine) == 0:print("None")return
  • 如果 combine 为空，说明没有找到任何交集区间，则输出 "None" 并退出函数。
4. 合并交集区间
python">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。

代码的整体逻辑

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

时间复杂度分析

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

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

示例

输入：
4
1 3
2 5
6 8
7 9
输出：
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++ 代码讲解

  1. 输入部分：

    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 中。

  2. 排序部分：

    sort(ranges.begin(), ranges.end());
    • 使用 std::sort 对 ranges 进行排序，排序依据是区间的起始位置（ranges[i].first）。因为 std::sort 默认是升序排序，所以我们无需额外指定排序规则。

  3. 计算交集：

    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。

  4. 没有交集时输出 “None”：

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

  5. 合并交集区间：

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

  6. 主函数：

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

为什么刷题很重要？

  1. 机试是进入技术面的第一关：
    华为OD机试（常被称为机考）主要考察算法和编程能力。只有通过机试，才能进入后续的技术面试环节。

  2. 技术面试需要手撕代码：
    技术一面和二面通常会涉及现场编写代码或算法题。面试官会注重考察候选人的思路清晰度、代码规范性以及解决问题的能力。因此提前刷题、多练习是通过面试的重要保障。

  3. 入职后的可信考试：
    入职华为后，还需要通过“可信考试”。可信考试分为三个等级：

    • 入门级：主要考察基础算法与编程能力。
    • 工作级：更贴近实际业务需求，可能涉及复杂的算法或与工作内容相关的场景题目。
    • 专业级：最高等级，考察深层次的算法以及优化能力，与薪资直接挂钩。

刷题策略与说明：

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

  1. 关注历年真题：

    • 题库中的旧题占比较大，建议优先刷历年的A卷、B卷、C卷、D卷题目。
    • 对于每道题目，建议深度理解其解题思路、代码实现，以及相关算法的适用场景。

  2. 适应新题目：

    • E卷中包含全新题目，需要掌握全面的算法知识和一定的灵活应对能力。
    • 建议关注新的刷题平台或交流群，获取最新题目的解析和动态。

  3. 掌握常见算法：
    华为OD考试通常涉及以下算法和数据结构：

    • 排序算法（快速排序、归并排序等）
    • 动态规划（背包问题、最长公共子序列等）
    • 贪心算法
    • 栈、队列、链表的操作
    • 图论（最短路径、最小生成树等）
    • 滑动窗口、双指针算法

  4. 保持编程规范：

    • 注重代码的可读性和注释的清晰度。
    • 熟练使用常见编程语言，如C++、Java、Python等。

如何获取资源？

  1. 官方参考：

    • 华为招聘官网或相关的招聘平台会有一些参考信息。
    • 华为OD的相关公众号可能也会发布相关的刷题资料或学习资源。

  2. 加入刷题社区：

    • 找到可信的刷题交流群，与其他备考的小伙伴交流经验。
    • 关注知名的刷题网站，如LeetCode、牛客网等，这些平台上有许多华为OD的历年真题和解析。

  3. 寻找系统性的教程：

    • 学习一本经典的算法书籍，例如《算法导论》《剑指Offer》《编程之美》等。
    • 完成系统的学习课程，例如数据结构与算法的在线课程。

积极心态与持续努力：

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

考试注意细节

  1. 本地编写代码

    • 在本地 IDE（如 VS Code、PyCharm 等）上编写、保存和调试代码，确保逻辑正确后再复制粘贴到考试页面。这样可以减少语法错误，提高代码准确性。

  2. 调整心态，保持冷静

    • 遇到提示不足或实现不确定的问题时，不必慌张，可以采用更简单或更有把握的方法替代，确保思路清晰。

  3. 输入输出完整性

    • 注意训练和考试时都需要编写完整的输入输出代码，尤其是和题目示例保持一致。完成代码后务必及时调试，确保功能符合要求。

  4. 快捷键使用

    • 删除行可用 Ctrl+D，复制、粘贴和撤销分别为 Ctrl+C，Ctrl+V，Ctrl+Z，这些可以正常使用。
    • 避免使用 Ctrl+S，以免触发浏览器的保存功能。

  5. 浏览器要求

    • 使用最新版的 Google Chrome 浏览器完成考试，确保摄像头开启并正常工作。考试期间不要切换到其他网站，以免影响考试成绩。

  6. 交卷相关

    • 答题前，务必仔细查看题目示例，避免遗漏要求。
    • 每完成一道题后，点击【保存并调试】按钮，多次保存和调试是允许的，系统会记录得分最高的一次结果。完成所有题目后，点击【提交本题型】按钮。
    • 确保在考试结束前提交试卷，避免因未保存或调试失误而丢分。

  7. 时间和分数安排

    • 总时间：150 分钟；总分：400 分。
    • 试卷结构：2 道一星难度题（每题 100 分），1 道二星难度题（200 分）。及格分为 150 分。合理分配时间，优先完成自己擅长的题目。

  8. 考试环境准备

    • 考试前请备好草稿纸和笔。考试中尽量避免离开座位，确保监控画面正常。
    • 如需上厕所，请提前规划好时间以减少中途离开监控的可能性。

  9. 技术问题处理

    • 如果考试中遇到断电、断网、死机等技术问题，可以关闭浏览器并重新打开试卷链接继续作答。
    • 出现其他问题，请第一时间联系 HR 或监考人员进行反馈。

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


http://www.ppmy.cn/server/159568.html

相关文章

SparkSQL函数

SparkSQL函数

文章目录 1. SparkSQL函数概述2. SparkSQL内置函数2.1 常用内置函数分类2.2 常用数组函数2.2.1 array()函数1. 定义2. 语法3. 示例 2.3 常用日期与时间戳函数2.4 常见聚合函数2.5 常见窗口函数 3. SparkSQL自定义函数3.1 自定义函数分类3.2 自定义函数案例演示 1. SparkSQL函数…
阅读更多...
在nvidia jetson nx 板子上使用VPI+cuda backend计算光流

在nvidia jetson nx 板子上使用VPI+cuda backend计算光流

nvida的VPI可以调用CPU、GPU、PVA、VIC、NVENC、OFA等后端资源。因此恰当的使用vpi可以把部分需要gpu的计算让其他的计算资源来承担来降低cpu的负载&#xff0c;降低cpu过载造成设备卡死、计算异常等各种各样的风险。 下面介绍一下使用VPIcuda backend 计算LK稀疏光流。nvidia官…
阅读更多...
Spark Streaming的核心功能及其示例PySpark代码

Spark Streaming的核心功能及其示例PySpark代码

Spark Streaming是Apache Spark中用于实时流数据处理的模块。以下是一些常见功能的实用PySpark代码示例&#xff1a; 基础流处理&#xff1a;从TCP套接字读取数据并统计单词数量 from pyspark import SparkContext from pyspark.streaming import StreamingContext# 创建Spar…
阅读更多...
windows蓝牙驱动开发-BLE音频(二)

windows蓝牙驱动开发-BLE音频(二)

详细设计 音频格式要求 音频帧持续时间 蓝牙 LE 音频配置文件允许实现支持音频帧持续时间为 7.5 毫秒或 10 毫秒的音频流式处理。 Windows 要求 IHV 提供的编解码器支持这两个帧持续时间&#xff0c;以确保与蓝牙 LE 音频配件设备的互操作性&#xff0c;并与连接到系统的其他…
阅读更多...
【Rust的2种线程锁 阻塞 vs 挂起】

【Rust的2种线程锁 阻塞 vs 挂起】

async_std::sync::Mutex 和 std::sync::Mutex 之间的主要区别在于它们如何处理线程阻塞和异步编程模型。以下是两者的关键差异&#xff1a; 标准库的 Mutex (std::sync::Mutex) 同步阻塞&#xff1a;当一个线程尝试获取 std::sync::Mutex 的锁时&#xff0c;如果锁已经被其他线…
阅读更多...
数字化时代，传统代理模式的变革之路

数字化时代，传统代理模式的变革之路

在数字化飞速发展的今天&#xff0c;线上线下融合&#xff08;O2O&#xff09;成了商业领域的大趋势。这股潮流&#xff0c;正猛烈冲击着传统代理模式&#xff0c;给它带来了新的改变。 咱们先看看线上线下融合现在啥情况。线上渠道那是越来越多&#xff0c;企业纷纷在电商平台…
阅读更多...
一文读懂单片机的串口

一文读懂单片机的串口

目录 串口通信的基本概念 串口通信的关键参数 单片机串口的硬件连接 单片机串口的工作原理 数据发送过程 数据接收过程 单片机串口的编程实现 以51单片机为例 硬件连接 初始化串口 发送数据 接收数据 串口中断服务函数 代码示例 单片机串口的应用实例 单片机与…
阅读更多...
第十二章：算法与程序设计

第十二章：算法与程序设计

文章目录&#xff1a; 一&#xff1a;基本概念 1.算法与程序 1.1 算法 1.2 程序 2.编译预处理 3.面向对象技术 4.程序设计方法 5.SOP标志作业流程 6.工具 6.1 自然语言 6.2 流程图 6.3 N/S图 6.4 伪代码 6.5 计算机语言 二&#xff1a;程序设计 基础 1.常数 …
阅读更多...
最新文章

Copyright @ 2022~2023