题目描述
blablabla
样例
import java.util.*;//导入Java的实用工具包
class Range implements Comparable<Range>{//定义了一个叫Range的类,并实现了comparable接口,以便能对Range对象进行排序
int l,r;//定义了两个整型变量,用于存储区间的两个端点
public Range(int l,int r){//定义了Range类的构造函数,接受两个参数,即区间的两个端点
this.l=l;//使用this关键字来区别成员变量和参数,将传上来的值赋值给成员变量l
this.r=r;//同上
}
public int compareTo(Range o){//重写了comparable接口中的compareTo方法,用于定义如何比较两个Range
return Integer.compare(r,o.r);//使用integer类中的compare方法去比较两个Range对象的r值
}
}
public class Main { // 定义了一个名为Main的公共类。
static int N = 100010, INF = 0x3f3f3f3f, n; // 定义了三个静态整型变量N、INF和n。N是一个大常数,INF是一个很大的数,n用于存储区间的数量。
static Range[] range = new Range[N]; // 定义了一个静态的Range数组,大小为N。因为数组的大小是固定的,所以必须定义为全局变量。
public static void main(String[] args) { // 定义了程序的入口点,即main方法。
Scanner scan = new Scanner(System.in); // 创建了一个Scanner对象,用于从标准输入读取数据。
n = scan.nextInt(); // 读取一个整数n,表示接下来要输入的区间数量。
for (int i = 0; i < n; i++) { // 循环n次,每次读取一个区间的左右端点。
int l = scan.nextInt(); // 读取区间的左端点。
int r = scan.nextInt(); // 读取区间的右端点。
range[i] = new Range(l, r); // 使用读取到的左右端点创建一个新的Range对象,并存储在range数组中。
}
// 对range数组中的Range对象进行排序,按照它们的r值从小到大排序。
// 第一个参数是待排序的数组,第二个和第三个参数定义了排序的范围(从0到n-1)。
// 最后一行代码被注释掉了,它提供了另一种排序方式,使用lambda表达式定义比较逻辑。
Arrays.sort(range, 0, n);
int res = 0; // 定义了一个整型变量res,用于存储需要的最少点数。
int ed = -INF; // 定义了一个整型变量ed,初始化为一个很大的负数,表示上一个点的右端点。
for (int i = 0; i < n; i++) { // 遍历排序后的range数组。
if (range[i].l > ed) { // 如果当前区间的左端点大于上一个点的右端点,说明需要一个新的点来覆盖这个区间。
res++; // 将res加1,表示需要一个新的点。
ed = range[i].r; // 更新ed为当前区间的右端点。
}
}
System.out.println(res); // 输出需要的最少点数。
}
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla