描述
某校大门外长度为L的马路上有一排树,每两棵相邻的树之间的间隔都是1米。
我们可以把马路看成一个数轴,马路的一端在数轴0的位置,另一端在L的位置;数轴上的每个整数点,即0,1,2,……,L,都种有一棵树。
由于马路上有一些区域要用来建地铁。
这些区域用它们在数轴上的起始点和终止点表示。
已知任一区域的起始点和终止点的坐标都是整数,区域之间可能有重合的部分。
现在要把这些区域中的树(包括区域端点处的两棵树)移走。
你的任务是计算将这些树都移走后,马路上还有多少棵树。
代码
暴力方法不解释。
区间合并方法:
时间复杂度nlogn,瓶颈在排序。
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int L = sc.nextInt();
int m = sc.nextInt();
ArrayList<Pair> segs = new ArrayList<>();
for(int i = 0; i < m; i++)
segs.add(new Pair(sc.nextInt(),sc.nextInt()));
ArrayList<Pair> ans = merge(segs); //合并后的区间
int size = ans.size();
int cnt = L + 1;
for(int i = 0; i < size; i++) {
Pair seg = ans.get(i);
cnt -= seg.r - seg.l + 1;
}
System.out.println(cnt);
}
static ArrayList<Pair> merge(ArrayList<Pair> segs) {
Collections.sort(segs);
ArrayList<Pair> ans = new ArrayList<>();
int st = -1, ed = -1; //0不行
for(Pair seg : segs) {
if(ed < seg.l) {
if(st != -1)
ans.add(new Pair(st,ed));
st = seg.l;
ed = seg.r;
} else ed = Math.max(ed,seg.r);
}
if(st != -1) ans.add(new Pair(st,ed));
return ans;
}
}
class Pair implements Comparable {
int l;
int r;
Pair(int l, int r) {
this.l = l;
this.r = r;
}
//这里必须是public!
public int compareTo(Object o) {
Pair pair = (Pair) o;
return l - pair.l;
}
}
可以优化一下,不用ArrayList,且在merge里产生新区间时顺便计算即可:
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int L = sc.nextInt();
int m = sc.nextInt();
Pair[] segs = new Pair[m];
for(int i = 0; i < m; i++)
segs[i] = new Pair(sc.nextInt(),sc.nextInt());
Arrays.sort(segs);
int sum = 0;
int st = segs[0].l, ed = segs[0].r;
for(int i = 1; i < m; i++) {
int l = segs[i].l, r = segs[i].r;
if(ed < l) {
sum += ed - st + 1;
st = l;
ed = r;
} else ed = Math.max(ed,r);
}
sum += ed - st + 1;
System.out.println(L + 1 - sum);
}
}
class Pair implements Comparable {
int l;
int r;
Pair(int l, int r) {
this.l = l;
this.r = r;
}
public int compareTo(Object o) {
Pair pair = (Pair) o;
return l - pair.l;
}
}
扩展
AcWing803. 区间合并
import java.util.Scanner;
import java.util.ArrayList;
import java.util.Collections;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
ArrayList<Pair> segs = new ArrayList<>();
for(int i = 0; i < n; i++) {
int l = sc.nextInt();
int r = sc.nextInt();
segs.add(new Pair(l,r));
}
int cnt = merge(segs);
System.out.println(cnt);
}
static int merge(ArrayList<Pair> segs) {
int cnt = 0;
Collections.sort(segs);
int st = (int)-1e9, ed = (int)-1e9;
for(Pair seg : segs) {
if(seg.l > ed) {
cnt++;
st = seg.l;
ed = seg.r;
} else ed = Math.max(ed,seg.r);
}
return cnt;
}
}
class Pair implements Comparable {
int l;
int r;
Pair(int l, int r) {
this.l = l;
this.r = r;
}
//这里必须是public!
public int compareTo(Object o) {
Pair pair = (Pair) o;
return l - pair.l;
}
}
结合本题和上题基本上可以覆盖所有情形了。
AcWing1343. 挤牛奶
每天早上 5 点,三名农夫去牛场给奶牛们挤奶。
现在从 5 点开始按秒计时,第一名农夫在第 300秒开始给牛挤奶,并在第 1000 秒停止挤奶。
第二名农夫在第 700 秒开始给牛挤奶,并在第 1200 秒停止挤奶。
第三名农夫在第 1500 秒开始给牛挤奶,并在第 2100秒停止挤奶。
从开始挤奶到挤奶完全结束,这一期间,至少存在一名农夫正在挤奶的连续时间段的长度最长为 900 秒(第 300秒至第 1200秒),完全没有任何农夫在挤奶的连续时间段的长度最长为 300 秒(第 1200秒至第 1500 秒)。
现在给你 N 名农夫挤 N 头奶牛的工作时间表,请你求出:
- 至少存在一名农夫正在挤奶的连续时间段的最长长度。
- 没有任何农夫在挤奶的连续时间段的最长长度。
import java.util.Scanner;
import java.util.Arrays;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
Pair[] segs = new Pair[n];
for(int i = 0; i < n; i++) segs[i] = new Pair(sc.nextInt(),sc.nextInt());
Arrays.sort(segs);
int st = segs[0].l, ed = segs[0].r, lenY = ed - st, lenN = 0;
for(int i = 0; i < n; i++) {
int l = segs[i].l, r = segs[i].r;
if(ed < l) {
lenY = Math.max(lenY, ed - st);
lenN = Math.max(lenN, l - ed);
st = l;
ed = r;
} else ed = Math.max(ed, r);
}
lenY = Math.max(lenY,ed- st);
System.out.println(lenY + " " + lenN);
}
}
class Pair implements Comparable {
int l;
int r;
Pair(int l, int r) {
this.l = l;
this.r = r;
}
public int compareTo(Object o) {
Pair pair = (Pair) o;
return l - pair.l;
}
}