问题描述
小H和小W来到了一条街上,两人分开买菜,他们买菜的过程可以描述为,去店里买一些菜然后去旁边的一个广场把菜装上车,两人都要买n种菜,所以也都要装n次车。具体的,对于小H来说有n个不相交的时间段[a1,b1],[a2,b2]…[an,bn]在装车,对于小W来说有n个不相交的时间段[c1,d1],[c2,d2]…[cn,dn]在装车。其中,一个时间段[s, t]表示的是从时刻s到时刻t这段时间,时长为t-s。
由于他们是好朋友,他们都在广场上装车的时候会聊天,他们想知道他们可以聊多长时间。
输入格式
输入的第一行包含一个正整数n,表示时间段的数量。
接下来n行每行两个数ai,bi,描述小H的各个装车的时间段。
接下来n行每行两个数ci,di,描述小W的各个装车的时间段。
输出格式
输出一行,一个正整数,表示两人可以聊多长时间。
样例输入
4
1 3
5 6
9 13
14 15
2 4
5 7
10 11
13 14
样例输出
3
数据规模和约定
对于所有的评测用例,1 ≤ n ≤ 2000, ai < bi < ai+1,ci < di < ci+1,对于所有的i(1 ≤ i ≤ n)有,1 ≤ ai, bi, ci, di ≤ 1000000。
测试评分:100
总结:此题容易犯两个错误
(1)利用大量的if和else来判断起点和终点来计算重合的时间,这样考试时间浪费了,虽然可以得到更加优化的结果,但是考试需要花费大量的时间在ifelse的判断上,亲测,如果使用elseif判断可能有几十个if和else才能解决问题。
(2)因为写过大量的工程类的题目所以经常为了尽量解耦的代码。初始化的数据放在一个数组中,处理使用另外一个阶段或者是一个方法中,这样子会加大时间复杂,下面的代码在初始化H数组和M数组的时候就对timeCount这个数组进行了相关处理,而不是先初始化M和H数组,然后二阶段传入一个H和M数组,再根据H和M种的数据进行处理timeCount,这个做法恰好可以使这个代码不超时,可以增加20分的总分。
import java.util.Arrays;
import java.util.Scanner;
/*
* @author qianliu on 2019/3/7 13:32
* @Discription:
* 1.总结:初始化数据的时候进行一些操作比test2那种先初始到数组,以后在处理时间复杂度低,不容易超时,
* 已经第二次因为这种事而超时了
*/
public class Main {
public static void main(String[] args) {
//初始化数据
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
//H卸货
int H[][] = new int[n][2];
//M卸货
int M[][] = new int[n][2];
int totalTime = 0; //总时间
int timeCount[] = new int[1000000];
Arrays.fill(timeCount,0); //timeCount全部初始化为0
for (int i = 0; i < n ; i++) {
H[i][0] = scanner.nextInt();
H[i][1] = scanner.nextInt();
//历H和M找到重复的时间段
for (int j = H[i][0]; j < H[i][1]; j++) {
timeCount[j]++;
}
}
for (int i = 0; i < n ; i++) {
M[i][0] = scanner.nextInt();
M[i][1] = scanner.nextInt();
//历H和M找到重复的时间段
for (int j = M[i][0]; j < M[i][1]; j++) {
timeCount[j]++;
}
}
//找到timeCount[]中为2的元素
for (int i = 0; i < Math.min(H[n-1][1],M[n-1][1]); i++) {
if(timeCount[i] == 2){
totalTime++;
}
}
//3.输出
System.out.println(totalTime);
}
}