正经题解｜小明同学的仓鼠

题目解析

对于记录我们要做三次动作，"修正"开始时间与结束时间，按照记录开始时间排升序，合并重叠的区间。

AC代码

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const int N = 1e5 + 10;
int t,n;
struct node {
    int s,e;
}a[N];
node *b[N];
bool cmp(node x,node y) {
    return x.s < y.s;
}
int main() {
    int sh,sm,eh,em;
    scanf("%d",&n);
    for(int i=0;i<n;i++) {
        scanf("%2d%2d-%2d%2d",&sh,&sm,&eh,&em);
        sm = (sm / 5) * 5;
        em = (em + 4) / 5 * 5;
        if (em >= 60) {
            em %= 60;
            eh++;
        }
        eh %= 25;
        a[i].s = sh * 60 + sm;
        a[i].e = eh * 60 + em;
    }
    sort(a,a+n,cmp);
    int j = 0;
    for(int i=1;i<=n;i++) {
        if (i == n){
            b[j++] = &a[i-1];
            break;
        }
        node *cur = &a[i];
        node *pre = &a[i-1];
        if (cur->s >= pre->s && cur->s <= pre->e) {
            cur->s = pre->s;
            cur->e = max(cur->e,pre->e);
        }else {
            b[j++] = pre;
        }
    }
    for(int i=0;i<j;i++){
        printf("%02d%02d-%02d%02d\n",b[i]->s/60,b[i]->s %60,b[i]->e/60,b[i]->e %60);
    }
    return 0;
}

复杂度

区间合并：$O(n)$