区间相交问题 给定x轴上的n个闭区间，去掉尽可能少的闭区间，使得剩下的闭区间都不相交。对于给定的n个闭区间，计算去掉的最少的闭区间数。 输入描述：对于每组输入数据，输入数据的第一行是正整数n(1<=n<=40000)，表示闭区间数，在接下来的n行中，每行有两个整数，分别表示闭区间的两个端点。 输出描述：输出计算出的去掉的最少闭区间数。 输入样例： 3 10 20 15 10 20 15 样例输出： 2编写完整代码用贪心算法实现

这道题可以用贪心算法。首先按照区间右端点从小到大排序，然后从左到右扫描所有区间，只要当前区间与前一个区间不相交，则保留当前区间，否则去掉当前区间。最后剩下的区间数就是最少去掉的区间数。

下面是Python代码实现：

n = int(input())
intervals = []
for i in range(n):
    l, r = map(int, input().split())
    intervals.append((l, r))

intervals.sort(key=lambda x: x[1])  # 按右端点排序

cnt = 1
last_end = intervals[0][1]
for i in range(1, n):
    if intervals[i][0] > last_end:  # 当前区间与前一个区间不相交
        cnt += 1
        last_end = intervals[i][1]

print(n - cnt)  # 去掉的区间数

时间复杂度为 $O(n\log n)$，因为需要排序。