我正在解决一个问题,我的问题是在某个测试中出现TL(时间限制)错误(代码在条件之后呈现),我不知道如何加速算法以便测试通过,也许我的逻辑有问题——我无法否认这一点。
问题条件:给定两个数组a和b,长度为N,由整数组成。考虑一个由连接点 (0, ai) 和 (1, bi) 的线段组成的集合,其中 1 <= i <= N。找出该集合中不与其他线段相交的线段的数量。
相交是指至少有一个公共点的线段,即具有相同端点的线段相交。
输入格式
在第一行中输入 N (1 <= N <= 3 * 10^5) - 段数。接下来,N 行包含由空格 ai 和 bi 分隔的 2 个整数(1 <= ai, bi <= 2 * N),指定第 i 段的坐标。保证输入中指定的所有段都不同,即对于 i != j,至少满足条件 ai != aj 和 bi != bj 之一
代码:
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Map<Integer, ArrayList<Integer>> nums = new HashMap<>();
int amount = sc.nextInt();
sc.nextLine();
for (int i = 0; i < amount; i++) {
String[] point = sc.nextLine().split(" ");
int x = Integer.parseInt(point[0]);
int y = Integer.parseInt(point[1]);
if (!nums.containsKey(x)) {
nums.put(x, new ArrayList<>());
}
nums.get(x).add(y);
}
int count = 0;
for (int key1 : nums.keySet()) {
boolean intersects = false;
ArrayList<Integer> values1 = nums.get(key1);
for (int key2 : nums.keySet()) {
if (key1 != key2) {
ArrayList<Integer> values2 = nums.get(key2);
for (int value1 : values1) {
for (int value2 : values2) {
if ((key1 < key2 && value1 >= value2) || (key1 > key2 && value2 >= value1)) {
intersects = true;
break;
}
}
if (intersects) {
break;
}
}
if (intersects) {
break;
}
}
}
if (!intersects) {
count++;
}
}
System.out.println(count);
}
}