猿辅导8.1笔试
笔试后两题都看不懂，题目那么长，也是醉了，看都不想看，第一题改了半天才AC。
最后时刻想到用数组代替了map才没有超时。非科班小白。
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Set;
/**
* @Description:上猿辅导课所需要的超能力（醉）
* @Create 2020-08-01 19:21
* @Email:1173748742@qq.com
*/
public class YuanTest1 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s = null;
while ((s = br.readLine()) != null) {
int N = Integer.valueOf(s);
int[][] arr = new int[N][2];
int max = 0;
int min = Integer.MAX_VALUE;
for (int i = 0; i < N; i++) {
String[] s1 = br.readLine().split(" ");
arr[i][0] = Integer.valueOf(s1[0]);
arr[i][1] = Integer.valueOf(s1[1]);
max = Math.max(max, arr[i][1]);
min = Math.min(min, arr[i][0]);
}
//int res = function(arr, N, min, max);
// int res = function2(arr);
int res = function3(arr, min, max);
System.out.println(res);
}
br.close();
}
/**
* 最后想到用数组代替map AC
* <p>
* 主要可能还是map存和取太费时间了吧
*
* @param arr
* @param min
* @param max
* @return */
private static int function3(int[][] arr, int min, int max) {
int[] map = new int[max - min + 1];
for (int[] tmp : arr) {
int star = tmp[0], end = tmp[1];
for (int i = star; i < end; i++) {
map[i - min]++;
}
}
int res = 0;
for (int t : map) {
res = Math.max(res, t);
}
if (res == 0) return 1;
return res;
}
/**
* 用数据结构 还是超时，不过和第一次思路没什么区别
*
* @param arr
* @return */
private static int function2(int[][] arr) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int[] tmp : arr) {
int star = tmp[0], end = tmp[1];
for (int i = star; i < end; i++) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
}
Set<Integer> integers = map.keySet();
int res = 0;
for (int t : integers) {
res = Math.max(res, map.get(t));
}
return res;
}
/**
* 最开始思路 超时
* 想过在步数上优化 还是超时
*
* @param arr
* @param n
* @param min
* @param max
* @return */
private static int function(int[][] arr, int n, int min, int max) {
int res = 0;
int tmp = 0;
for (int i = min; i <= max; ) {
tmp = 0;
int nextSetp = Integer.MAX_VALUE;
for (int j = 0; j < n; j++) {
if (arr[j][0] <= i && i < arr[j][1]) {
tmp++;
}
if (arr[j][0] > i) {
nextSetp = Math.min(nextSetp, arr[j][0] - i);
}
if (arr[j][1] > i) {
nextSetp = Math.min(nextSetp, arr[j][1] - i);
}
}
res = Math.max(res, tmp);
if (nextSetp == Integer.MAX_VALUE) {
i++;
} else {
i += nextSetp;
}
}
return res;
}
} 
