Skip to content

11262: 【原1262】Milking Cow

题目

题目描述

author: shiyinchun 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1262

Description

瓦特尔,阿隆索,汉密尔顿在F1上海站进行比赛,每人必须进维修站更换轮胎一次(谁出的无聊规定?!),而且只能进维修站一次。

阿隆索在20秒进站换胎,一直到90秒出站。瓦特尔在60秒开始进站,在 130秒结束。汉密尔顿在160秒开始220秒结束。期间最长的至少有一个车手在维修区的连续时间为110秒(从20秒到130秒),而最长的无人在维修区的连续时间(从有人进维修站开始一直到出维修站)为30秒(从130秒到160秒)。

假设现在又进行了一场有N个车手的比赛,你的任务是编一个程序,读入一个有N个车手(1 <= N <= 5000)进N次站的工作时间列表,计算以下两点(均以秒为单位):

最长至少有一人在维修站内的时间段。

最长的无人在维修站的时间段。(从有人进站开始算起)

Input Format

第1行:一个整数N。

第2至第N+1行:每行两个小于1000000的非负整数,表示一个车手的进站时刻与出站时刻。

Output Format

一行,两个整数,即题目所要求的两个答案。

Sample Input

3
200 900
600 1300
1600 2200

Sample Output

1100 300

yyong119's solution

#include <cstdio>
#include <algorithm>
using namespace std;

struct node {
    int inTime, outTime;
}a[5005];

bool cmp(const node &p, const node &q) {
    return p.inTime < q.inTime;
}

int main() {

    int n; scanf("%d", &n);
    for (int i = 0; i < n; ++i) scanf("%d%d", &a[i].inTime, &a[i].outTime);
    sort(a, a + n, cmp);
    int maxNotEmptyTime = 0, maxEmptyTime = 0;
    int currentStart = a[0].inTime, currentEnd = a[0].outTime;
    for (int i = 1; i < n; ++i) {
        if (a[i].inTime > currentEnd) {
            maxNotEmptyTime = max(maxNotEmptyTime, currentEnd - currentStart);
            maxEmptyTime = max(maxEmptyTime, a[i].inTime - currentEnd);
            currentStart = a[i].inTime;
        }
        currentEnd = max(currentEnd, a[i].outTime);
    }
    maxNotEmptyTime = max(maxNotEmptyTime, currentEnd - currentStart);
    printf("%d %d\n", maxNotEmptyTime, maxEmptyTime);
    return 0;
}