题目解析
给定n个时间段求出 这些在一天中未出现的时间段
解题思路
将时间段转为秒的形式存储
(如 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;
}
@Override
public 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);
}