?Hello!这里是欧_aita的博客。
?今日语录: 成功的关键在于对目标的持久追求。
?个人主页:欧_aita
ψ(._. )>?个人专栏:
数据结构与算法
数据库
- 合并重叠区间: 将给定的一组区间合并成尽可能少的不相交或相邻的区间。
- 区间调度: 在一系列任务或活动中,每个任务有一个开始时间和结束时间,选择尽可能多的任务而不相互冲突。
- 时间区间问题: 处理一系列时间区间,例如查找某个时间点同时发生的事件。
- 日程安排: 对一组日程进行调度,以确定可以安排多少个活动而不冲突。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int, int> PII;
const int N = 100010;
int n;
vector<PII> segs;
// 区间合并后的区间个数
// 1. 按区间左端点排序
// 2. 左端点st 右端点ed
void merge(vector<PII>& segs) {
vector<PII> res;
sort(segs.begin(), segs.end());
int st = -2e9, ed = -2e9;
for (auto seg : segs)
if (ed < seg.first) {
if (st != -2e9) res.push_back(make_pair(st, ed));
st = seg.first, ed = seg.second;
} else
ed = max(ed, seg.second);
if (st != -2e9) res.push_back(make_pair(st, ed));
// 用合并后的区间更新原始向量
segs = res;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int l, r;
cin >> l >> r;
segs.push_back({l, r});
}
merge(segs);
cout << segs.size() << endl;
return 0;
}
sort(seg.begin(),seg.end());
这里的排序是通过vector数组中的pair数组中的first数据元素大小判断的。
#include <iostream>
#include <cstring>
using namespace std;
int main() {
char str[1000];
cout << "Enter a string: ";
fgets(str, sizeof(str), stdin);
int n = strlen(str);
for (int i = 0; str[i]; i++) {
int j = i;
while (j < n && str[j] != ' ') {
j++;
}
// 输出提取的单词
for (int k = i; k < j; k++) {
cout << str[k];
}
cout << endl;
i = j;
}
return 0;
}
for (int i = 0; str[i]; i++) {
int j = i;
while (j < n && str[j] != ' ') {
j++;
}
// 输出提取的单词
for (int k = i; k < j; k++) {
cout << str[k];
}
cout << endl;
i = j;
}
注意for循环的末端,将子序列的最后一个字符下标赋给了i,然后在for循环中i又+1就是下一个空格或者末端的位置
fgets(str, sizeof(str), stdin);:使用fgets函数从标准输入中读取用户输入的字符串,并存储到str数组中。sizeof(str)确保不会超出数组的边界。
在这个过程中不断计数,求取最长不重复数组长度。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n;
int a[N], s[N];
int main() {
cin >> n;
for (int i = 0; i < n; i++)cin >> a[i];
int res = 0;
for (int i = 0, j = 0; i < n; i++)
{
s[a[i]]++;
while(s[a[i]]>1)
{
s[a[j]]--;
j++;
}
res = max(res, i - j + 1);
}
cout << res << endl;
return 0;
}