区间合并算法: 时间复杂度 $O(nlogn)$ == 100 * log100 约等于 100 * 6.6438 = 600-700单位运算
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 105;
struct Interval {
int left;
int right;
bool operator< (const Interval& o) const {
return left < o.left;
}
} intervals[N];
int main() {
int m, n, l, r;
cin >> m >> n;
for (int i = 0; i < n; ++i) {
cin >> l >> r;
intervals[i].left = l, intervals[i].right = r;
}
sort(intervals, intervals + n);
int L = intervals[0].left, R = intervals[0].right;
int sum = 0;
for (int i = 1; i < n; ++i) {
Interval curr = intervals[i];
if (curr.left <= R)
R = max(R, curr.right);
else
sum += R - L + 1, L = curr.left, R = curr.right;
}
sum += R - L + 1;
cout << m + 1 - sum << endl;
return 0;
}
暴力解法: 时间复杂度 $O(M * L)$ 约等于1E6次单位运算
#include <iostream>
using namespace std;
const int N = 1E4 + 5;
bool st[N];
int L, M;
int main() {
cin >> L >> M;
for (int i = 0; i <= L; ++i) st[i] = true;
while (M--) {
int l, r;
cin >> l >> r;
for (int i = l; i <= r; ++i) st[i] = false;
}
int ans = 0;
for (int i = 0; i <= L; ++i) ans += st[i];
cout << ans << endl;
return 0;
}
用差分做不好吗
差分是什么? 不会