L2-042 老板的作息表 - java

L2-042 老板的作息表

Java (javac)
时间限制
900 ms
内存限制
128 MB

Python (python3)
时间限制
300 ms
内存限制
64 MB

其他编译器
时间限制
200 ms
内存限制

题目描述：

新浪微博上有人发了某老板的作息时间表，表示其每天 4:30 就起床了。但立刻有眼尖的网友问：这时间表不完整啊，早上九点到下午一点干啥了？

本题就请你编写程序，检查任意一张时间表，找出其中没写出来的时间段。

输入格式：
输入第一行给出一个正整数 N，为作息表上列出的时间段的个数。随后 N 行，每行给出一个时间段，格式为：
hh:mm:ss - hh:mm:ss
其中 hh、mm、ss 分别是两位数表示的小时、分钟、秒。第一个时间是开始时间，第二个是结束时间。题目保证所有时间都在一天之内（即从 00:00:00 到 23:59:59）；每个区间间隔至少 1 秒；并且任意两个给出的时间区间最多只在一个端点有重合，没有区间重叠的情况。

输出格式：
按照时间顺序列出时间表中没有出现的区间，每个区间占一行，格式与输入相同。题目保证至少存在一个区间需要输出。

输入样例：
8
13:00:00 - 18:00:00
00:00:00 - 01:00:05
08:00:00 - 09:00:00
07:10:59 - 08:00:00
01:00:05 - 04:30:00
06:30:00 - 07:10:58
05:30:00 - 06:30:00
18:00:00 - 19:00:00
输出样例：
04:30:00 - 05:30:00
07:10:58 - 07:10:59
09:00:00 - 13:00:00
19:00:00 - 23:59:59

给定n个时间段求出 这些在一天中未出现的时间段

emmmmmmm

将时间段转为秒的形式存储
(如 00:00:00 - 01:00:00 表示成 0 ~ 3600 形式)

然后按时间段的左区间排序
如果该区间的右半边能覆盖到下面的右端点 那么这两个时间段为一起的 (如下图 橙色的线 与 红色的线 都是一个区间的)
否则就是两个时间段 (如下图 橙色的线 与 紫色的线 不是一个区间的)

如果当前是一个区间的话 那么这个区间的左半边不动 右半边去扩
否则 输出区间 上一个区间的左半边道当前区间的右半边

这是可以重叠的时候的情况

不过本题呢是 并且任意两个给出的时间区间最多只在一个端点有重合，没有区间重叠的情况

所以最多只会有存在两个区间的 左边的右端点 和 右边的左区间 的 点 重叠

所以只需要判断前后两个区间的相邻的部分是否重叠即可

ac

import java.io.*;
import java.math.*;
import java.util.*;public class Main
{public static void main(String[] args) throws IOException{int n = Integer.valueOf(sc.readLine());String l[] = new String[n + 10], r[] = new String[n + 10];for (int i = 1; i <= n; i++){String s[] = sc.readLine().split(" ");l[i] = s[0];r[i] = s[2];}Arrays.sort(l, 1, n + 1);Arrays.sort(r, 1, n + 1);if (!l[1].equals("00:00:00"))out.println("00:00:00 - " + l[1]);for (int i = 2; i <= n; i++){if (!r[i - 1].equals(l[i]))out.println(r[i - 1] + " - " + l[i]);}if (!r[n].equals("23:59:59"))out.printf(r[n] + " - 23:59:59");out.flush();out.close();}static BufferedReader sc = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(System.out);
}

可以重叠的

不过java会t

import java.io.*;
import java.math.*;
import java.util.*;public class Main
{static class edge implements Comparable<edge>{int l, r;public edge(int l, int r){this.l = l;this.r = r;}@Overridepublic int compareTo(edge other){if (this.l != other.l)return this.l - other.l;return this.r - other.r;}}static int tos(int a, int b, int c){return a * 60 * 60 + b * 60 + c;}static int toint(String times){String time[] = times.split(":");int a = Integer.valueOf(time[0]);int b = Integer.valueOf(time[1]);int c = Integer.valueOf(time[2]);return tos(a, b, c);}static String toString(int x){int a = x / 60 / 60;int b = x / 60 % 60;int c = x % 60;return String.format("%02d:%02d:%02d", a, b, c);}public static void main(String[] args){int n = sc.nextInt();sc.nextLine();edge shu[] = new edge[n + 10];for (int i = 1; i <= n; i++){String str = sc.nextLine();String s[] = str.split(" - ");shu[i] = new edge(toint(s[0]), toint(s[1]));}Arrays.sort(shu, 1, n + 1);int l = shu[1].l, r = shu[1].r;if (l != 0)out.printf("%s - %s\n", toString(0), toString(l));int L = r;for (int i = 2; i <= n; i++){int x = shu[i].l, y = shu[i].r;if (x <= r)r = Math.max(r, y);else{out.printf("%s - %s\n", toString(L), toString(x));l = x;r = y;}L = r;}if (L != tos(23, 59, 59))out.printf("%s - %s\n", toString(L), toString(tos(23, 59, 59)));out.flush();out.close();}static Scanner sc = new Scanner(System.in);static PrintWriter out = new PrintWriter(System.out);
}

split

对象数组排序
对象排序
对象排序

如果有说错的 或者 不懂的 尽管提 嘻嘻

一起进步！！！

闪现