13011: 【原3011】Coding Day

题目

题目描述

author: fzy 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/3011

Description

三个码农每天清晨起床，然后去公司写代码。第一个码农在400时刻开始干活，一直干到1100时刻。第二个码农在700时刻开始，在1200时刻结束。第三个码农在1500时刻开始2100时刻结束。期间最长的至少有一个码农在工作的连续时间为800秒(从400时刻到1200时刻)，而最长的无人工作的连续时间为300秒(从1200时刻到1500时刻)。

你的任务是编一个程序，读入一个有N个码农(1 <= N <= 5000)的工作时间列表，计算以下两点(均以秒为单位): 最长至少有一人在工作的时间段。 最长的无人工作的时间段。

Input Format

Line 1:     一个整数N。
Lines 2..N+1:   每行两个小于1000000的非负整数，表示一个码农的开始时刻与结束时刻。

Output Format

一行，两个整数，空格分隔，即题目所要求的两个答案。

Sample Input

3
400 1100
700 1200
1500 2100

Sample Output

800 300

yyong119's solution

#include <cstdio>
#include <algorithm>
#define MAX_N 5010
using namespace std;
struct Node {
    int l, r;
    bool operator<(const Node &p) const {
        return l == p.l ? r < p.r : l < p.l;
    }
} a[MAX_N];
int n, max_f, max_e;
inline int read() {
    char ch = getchar(); int res = 0, flag = 1;
    while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();
    if (ch == '-') flag = -1, ch = getchar();
    while (ch >= '0' && ch <= '9')
        res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return res * flag;
}
int main() {
    n = read();
    for (register int i = 0; i < n; ++i)
        a[i].l = read(), a[i].r = read();
    sort(a, a + n);
    int cur_l = a[0].l, cur_r = a[0].r;
    for (register int i = 1; i < n; ++i)
        if (a[i].l > cur_r) {
            max_e = max(max_e, a[i].l - cur_r);
            max_f = max(max_f, cur_r - cur_l);
            cur_l = a[i].l;
            cur_r = a[i].r;
        }
        else cur_r = max(cur_r, a[i].r);
    max_f = max(max_f, cur_r - cur_l);
    printf("%d %d", max_f, max_e);
    return 0;
}