# 2023华为OD机试真题【区间交叠/贪心算法】【Python Java】

## 题目描述

x和y 分别表示起点和终点，取值范围是[-10^5 ，10^5]。

3
1,4
2,5
3,6

2

## 视频讲解

2023华为机试真题【区间交叠/贪心算法】

## 示例代码（Java版本）

``````import java.util.LinkedList;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);

int n = sc.nextInt();
sc.nextLine();

Integer[][] segs = new Integer[n][];
for (int i = 0; i < n; i++) {
segs[i] = getSeg(sc.nextLine());
}

sort(segs);

System.out.println(coverSegs.size());
}

private static Integer[] getSeg(String line) {
String[] parts = line.split(",");
return new Integer[]{Integer.parseInt(parts[0]), Integer.parseInt(parts[1])};
}

private static void sort(Integer[][] segs) {
Arrays.sort(segs, (a, b) -> a[0].compareTo(b[0]));
}

private static LinkedList<Integer[]> cover(Integer[][] segs) {

for (int i = 1; i < segs.length; i++) {
while (true) {
if (stack.isEmpty()) {
break;
}

Integer[] top = stack.getLast();
Integer[] cur = segs[i];

if (cur[0] <= top[0]) {
if (cur[1] <= top[0]) {
break;
} else if (cur[1] < top[1]) {
break;
} else {
stack.removeLast();
}
} else if (cur[0] < top[1]) {
if (cur[1] <= top[1]) {
break;
} else {
break;
}
} else {
break;
}
}
}

return stack;
}
}

``````

## 示例代码（Python版本）

``````def get_segs(line):
parts = line.split(",")
return [int(parts[0]), int(parts[1])]

def sort_segs(segs):
return sorted(segs, key=lambda x: x[0])

def cover(segs):
stack = [segs[0]]

for i in range(1, len(segs)):
while True:
if not stack:
stack.append(segs[i])
break

top = stack[-1]
cur = segs[i]

if cur[0] <= top[0]:
if cur[1] <= top[0]:
break
elif cur[1] < top[1]:
break
else:
stack.pop()
elif cur[0] < top[1]:
if cur[1] <= top[1]:
break
else:
stack.append([top[1], cur[1]])
break
else:
stack.append(cur)
break

return stack

if __name__ == '__main__':
n = int(input())
segs = [get_segs(input()) for _ in range(n)]
sorted_segs = sort_segs(segs)
cover_segs = cover(sorted_segs)

print(len(cover_segs))

``````

THE END

)">