目录

一、小M的多任务下载器挑战

题目背景

题目内容

数据输入

数据输出

数据与约定

示例1

示例2

解题思路：

问题理解

数据结构选择

算法步骤

最终代码：

运行结果：

二、版本号比较 

问题描述

样例

示例 1:

示例 2:

示例 3:

示例 4：

 解题思路：

最终代码：

运行结果：

---

一、小M的多任务下载器挑战

题目背景

小M的程序设计大作业是编写一个多任务下载器，在做到计算任务并发数的时候遇到了困难。

题目内容

在一次下载中，总共包含N个任务，每个任务会在第x秒开始、并持续y秒。
小M想要知道，在一次下载中，同时最多会有多少个任务正在下载。

数据输入

第一行输入一个正整数N，代表总共有N个任务。
之后共N行，每行包含两个正整数x、y，x代表任务的开始时间，y代表任务的持续时间。

数据输出

输出包含一个整数，代表最高的任务并发数。

数据与约定

对于30%的数据，1 ≤ N ≤ 1,000，1 ≤ x, y ≤ 1,000。
对于50%的数据，1 ≤ N ≤ 1,000,000，1 ≤ x, y ≤ 1,000,000。
对于100%的数据，1 ≤ N ≤ 1,000,000，1 ≤ x, y ≤ 1,000,000,000。

示例1

输入
2
1 2
2 3

输出
2

说明
第一个任务在第一秒开始，持续两秒；第二个任务在第二秒开始，持续三秒。故在第二秒时有两个任务同时在进行，最大并发数为2。

示例2

输入
4
1 2
2 3
3 5
4 3

输出
3

说明
4个任务的时间区间分别为[1,2], [2,4], [3,7], [4,6]。
故在第4秒的时候，第2、3、4号任务正在进行。

解题思路：

问题理解

我们需要计算在一次下载中，同时最多会有多少个任务正在下载。每个任务有一个开始时间和持续时间，这意味着每个任务有一个开始时间和结束时间。

数据结构选择

为了有效地计算并发任务数，我们可以使用以下数据结构：

1. 事件列表：记录每个任务的开始和结束时间。
2. 时间线扫描：通过扫描时间线来计算每个时间点的并发任务数。

算法步骤

1. 事件记录：

   • 对于每个任务，记录其开始时间和结束时间。
   • 将开始时间视为“+1”事件，结束时间视为“-1”事件。

2. 时间线扫描：

   • 将所有事件（开始和结束）按时间顺序排序。
   • 遍历排序后的事件列表，维护一个计数器来记录当前并发任务数。
   • 每当遇到一个开始事件，计数器加1；每当遇到一个结束事件，计数器减1。
   • 在遍历过程中，记录计数器的最大值，即为最高的任务并发数。

最终代码：

 

#include <iostream>
#include <vector>
#include <algorithm>int solution(int n, std::vector<std::vector<int>> array) {std::vector<std::pair<int, int>> events;// 记录每个任务的开始和结束事件for (auto& task : array) {int start = task[0];int end = task[0] + task[1];events.push_back({start, 1});  // 开始事件events.push_back({end, -1});   // 结束事件}// 按时间顺序排序事件std::sort(events.begin(), events.end());int max_concurrent = 0;int current_concurrent = 0;// 遍历事件列表，计算并发任务数for (auto& event : events) {current_concurrent += event.second;max_concurrent = std::max(max_concurrent, current_concurrent);}return max_concurrent;
}int main() {// Add your test cases herestd::cout << (solution(2, {{1,2}, {2,3}}) == 2) << std::endl;std::cout << (solution(4, {{1,2}, {2,3}, {3,5}, {4,3}}) == 3) << std::endl;return 0;
}

运行结果：

 

二、版本号比较 

 

问题描述

给你两个版本号 version1 和 version2，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 . 连接。每个修订号由多位数字组成，可能包含前导零。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0，下一个修订号下标为 1，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。也就是说，修订号 1 和修订号 001 相等。如果版本号没有指定某个下标处的修订号，则该修订号视为 0。例如，版本 1.0 小于版本 1.1，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1，0 < 1。

返回规则如下：

• 如果 version1 > version2 返回 1，
• 如果 version1 < version2 返回 -1，
• 除此之外返回 0。

样例

示例 1:

输入:

version1 = "0.1"  
version2 = "1.1"

输出:

-1

示例 2:

输入:

version1 = "1.0.1"  
version2 = "1"

输出:

1

示例 3:

输入:

version1 = "7.5.2.4"  
version2 = "7.5.3"

输出:

-1

示例 4：

输入：

version1 = "1.0"  
version2 = "1.0.0"

输出：

0

解释：version1 没有第三级修订号，这意味着它的第三级修订号默认为 0。

 解题思路：

1. 理解版本号的结构：

   • 版本号由多个修订号组成，修订号之间用 . 分隔。
   • 每个修订号是一个整数，可能包含前导零。

2. 比较版本号：

   • 从左到右依次比较每个修订号。
   • 如果某个版本号缺少修订号，则视为 0。
   • 比较修订号时，忽略前导零。

3. 算法步骤：

   • 将版本号字符串按 . 分割成修订号数组。
   • 逐个比较修订号数组中的元素。
   • 如果某个修订号数组较短，则在其后补 0 进行比较。
   • 根据比较结果返回 1、-1 或 0。

最终代码：

#include <iostream>
#include <string>
#include <vector>
#include <sstream>// 辅助函数：将版本号字符串分割并转换为整数数组
std::vector<int> splitAndConvert(std::string version) {std::vector<int> result;std::stringstream ss(version);std::string token;while (std::getline(ss, token, '.')) {result.push_back(std::stoi(token));}return result;
}int solution(std::string version1, std::string version2) {// 将版本号按 `.` 分割成修订号数组std::vector<int> v1 = splitAndConvert(version1);std::vector<int> v2 = splitAndConvert(version2);// 逐个比较修订号int n = std::max(v1.size(), v2.size());for (int i = 0; i < n; ++i) {int num1 = (i < v1.size()) ? v1[i] : 0;int num2 = (i < v2.size()) ? v2[i] : 0;if (num1 > num2) return 1;if (num1 < num2) return -1;}return 0;
}int main() {// Add your test cases herestd::cout << (solution("0.1", "1.1") == -1) << std::endl;std::cout << (solution("1.0.1", "1") == 1) << std::endl;std::cout << (solution("7.5.2.4", "7.5.3") == -1) << std::endl;std::cout << (solution("1.0", "1.0.0") == 0) << std::endl;return 0;
}

运行结果：