简答题
偏难
#7256
课程冲突 小 A 修了 n 门课程, 第 i 门课程是从第 a i 天一直上到第 b i 天。 定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。 例如…
课程冲突
小 A 修了 n 门课程, 第 i 门课程是从第 ai 天一直上到第 bi 天。
定义两门课程的冲突程度为 : 有几天是这两门课程都要上的。
例如 a1=1,b1=3,a2=2,b2=4 时, 这两门课的冲突程度为 2。
现在你需要求的是这 n 门课中冲突程度最大的两门课的冲突程度。
时间限制:1000
内存限制:65536
输入
第一行一个正整数 n 表示课程数量。接下来 n 行,每行两个正整数 ai,bi。 2 ≤ n≤ 1000, 1 ≤ai ≤bi ≤ 1000。
输出
输出一个整数表示最大的冲突程度。
样例输入
3 1 3 2 4 5 5
样例输出
2
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">#include <bits/stdc++.h>
using namespace std;
// #define PPYDEBUG
struct lesson {
int no; // 课程编号
int a; // 课程开始a天
int b; // 课程结束b天
};
int max_chongtu(lesson x, lesson y) {
int r = min(x.b, y.b) - max(x.a, y.a) + 1;
if (r < 0) {
r = 0;
}
#ifdef PPYDEBUG
printf("%d = x[%d,%d] - y[%d,%d]\n", r, x.a, x.b, y.a, y.b);
#endif
return r;
}
int main() {
#ifdef LOCAL
freopen("202209_3_1.in", "r", stdin);
#endif
int n;
scanf("%d", &n);
lesson le[1010];
for (int i = 0; i < n; i++) {
le[i].no = i + 1;
scanf("%d%d", &le[i].a, &le[i].b);
}
int r = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
r = max(r, max_chongtu(le[i], le[j]));
}
}
printf("%d", r);
return 0;
}</pre>
这道题暂未补解析。