Java 之后学习题目以后,尽可能翻译一个java的版本
题目描述
给定 n 个区间 [li,ri],要求合并所有有交集的区间。
注意如果在端点处相交,也算有交集。
输出合并完成后的区间个数。
例如:[1,3] 和 [2,6] 可以合并为一个区间 [1,6]。
输入格式
第一行包含整数 n。
接下来 n 行,每行包含两个整数 l 和 r。
输出格式
共一行,包含一个整数,表示合并区间完成后的区间个数。
数据范围
1≤n≤100000,
−109≤li≤ri≤109
输入样例:
5
1 2
2 4
5 6
7 8
7 9
输出样例:
3
算法1
存储segs: ArrayList[HTML_REMOVED] 后面get花费时间O(1)
返回res: LinkedList[HTML_REMOVED] 添加add话费时间O(1)
- 排序
Collections.sort(segs, (o1, o2) -> o1[0] - o2[0]));
sges.sort(o1, o2) -> o1[0] - o2[0])); - 遍历每个seg
采取的策略: 如果当前的段和遍历的段,没有交集,则更新当前段以及添加当前段。
否则,代表当前段和遍历的段有交集,则更新当前段的ed字段。
参考文献
Y总视频
Java 代码
该代码是错误的,但是最后提交却是正确的,为什么呢? 因为第一次就把st, ed进行了更新,没有进行那个判断,然后如果后面有分割的段,则插入,即返回的res除了第一个段错误,后面的段是正确的结果。而最后的合并的区间的数量也是正确的
// 重铸java荣光
import java.util.*;
class Main {
public static List<int[]> merge(List<int[]> segs) {
List<int[]> res = new LinkedList<>();
Collections.sort(segs, (o1, o2) -> o1[0] - o2[0]);
int st = (int)-2e9, ed = (int)-2e9;
int n = segs.size();
for (int i = 0; i < n; i++) {
int[] cur = segs.get(i);
if (ed < cur[0]) {
st = cur[0];
ed = cur[1];
res.add(new int[]{st, ed});
} else {
ed = Math.max(cur[1], ed);
}
}
return res;
}
public static void main(String[] agrs) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<int[]> segs = new ArrayList<>();
while (n-- > 0) {
int[] tmp = new int[2];
tmp[0] = sc.nextInt();
tmp[1] = sc.nextInt();
segs.add(tmp);
}
System.out.println(merge(segs).size());
}
}
正确的代码
import java.util.*;
class Main {
public static List<int[]> merge(List<int[]> segs) {
List<int[]> res = new LinkedList<>();
Collections.sort(segs, (o1, o2) -> o1[0] - o2[0]);
int st = (int)-2e9, ed = (int)-2e9;
int n = segs.size();
for (int i = 0; i < n; i++) {
int[] cur = segs.get(i);
if (ed < cur[0]) {
if (st != (int)-2e9) {
res.add(new int[]{st, ed});
}
st = cur[0];
ed = cur[1];
} else {
ed = Math.max(cur[1], ed);
}
}
if (st != (int)-2e9) res.add(new int[]{st, ed});
return res;
}
public static void main(String[] agrs) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
List<int[]> segs = new ArrayList<>();
while (n-- > 0) {
int[] tmp = new int[2];
tmp[0] = sc.nextInt();
tmp[1] = sc.nextInt();
segs.add(tmp);
}
System.out.println(merge(segs).size());
}
}