AcWing 422. 校门外的树(区间合并)
原题链接
简单
作者:
Funnygo
,
2021-02-01 14:47:10
,
所有人可见
,
阅读 444
题目描述
算法1
(暴力枚举) $O(M*L)$
- boolean str[0,L]=true;
- 再另st[a.b]=false;
JAVA 代码
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
static int N=10010;
public static void main(String[] args){
int l = in.nextInt();
int m = in.nextInt();
boolean[] st = new boolean[N];
for(int i=0;i<=l;i++){
st[i]=true;
}
for(int i=0;i<m;i++){
int a = in.nextInt();
int b = in.nextInt();
for(int j=a;j<=b;j++){
st[j]=false;
}
}
int cnt=0;
for(int i=0;i<=l;i++){
if(st[i]) cnt++;
}
System.out.println(cnt);
}
}
算法2
(区间合并) $O(nlogn)$
二维数组排序讲解
Arrays.sort(s, (o1,o2)->(o1[0]-o2[0]));
- 将所有区间按左端点从小到大排序
- 从左到右遍历每个区间
(1)$l_{i}$<=R,则R=max(R,ri);
(2) $l_{i}$>R, 则将[L,R]存下,
且令L=$l_{i+1}$,R=$r_{i+1}$;
数组排序
JAVA 代码
import java.util.*;
public class Main{
static Scanner in = new Scanner(System.in);
public static void main(String[] args){
int n = in.nextInt();
int m = in.nextInt();
int[][] s = new int[m][2];
for(int i=0;i<m;i++){
s[i][0] = in.nextInt();
s[i][1] = in.nextInt();
}
Arrays.sort(s, (o1,o2)->(o1[0]-o2[0]));
int L=s[0][0],R=s[0][1],sum=0;
for(int i=1;i<m;i++){
if(s[i][0]<=R) R=Math.max(R,s[i][1]);
else{
sum+=R-L+1;
L=s[i][0];
R=s[i][1];
}
}
sum+=R-L+1;
System.out.println(1+n-sum);
}
}