原始问题
选择一个点在区间内 则说命中
有n个区间 最少的点 命中所有的区间 则最少是多少个点
分析
按结束的点 先后排序 先结束的总是在前面 总是选择 终点 为目标点
下一个区间的 s小于等于y(上一个区间的标注点) 就是命中(交叉or覆盖) ,因为拍过顺序,下一个区间的重终点一定一定大于上一个区间的 y
t 排序
依次选取最右的点
找 s>y=的
依次选终点
input
3
1 2 3
2 3 4
oupt:
2
3
ans:3
input
5
1 2 4 6 8
3 5 7 9 10
oupt
3
7
10
ans:3
贪心 尽量选择靠右的点

代码
package BlueCup.Eight_DP_greed;
import java.util.Scanner;
import static java.util.Arrays.sort;
public class 区间选点问题 {
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n = cin.nextInt();
int[] t = new int[n];
int[] s = new int[n];
Job[] jobs = new Job[n];
for (int i = 0; i < n; i++) {
s[i] = cin.nextInt();
}
for (int i = 0; i < n; i++) {
t[i] = cin.nextInt();
}
for (int i = 0; i < n; i++) {
jobs[i] = new Job(s[i], t[i]);
}
sort(jobs);
int res = f(jobs);
System.out.println("ans:"+res);
}
private static int f(Job[] jobs) {
int y = jobs[0].t;
int cnt = 1;
System.out.println(y);
for (int i = 1; i < jobs.length; i++) {
if (jobs[i].s >y) { //起始小于上次结束
cnt++;
y = jobs[i].t;
System.out.println(y);
}
}
return cnt;
}
private static class Job implements Comparable<Job> {
int s, t;
Job() {
}
/**
* @param s start
* @param t target
*/
public Job(int s, int t) {
this.s = s;
this.t = t;
}
//先比较后面的
public int compareTo(Job other) {
int x = this.t - other.t;
if (x == 0) {
return this.s - other.s;
}
return x;
}
}
}
本文作者:Author: 寒光博客
文章标题:[LanQiao]区间选点问题
本文地址:https://dxoca.cn/Algorithm/241.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。
本文地址:https://dxoca.cn/Algorithm/241.html 百度已收录
版权说明:若无注明,本文皆为“Dxoca's blog (寒光博客)”原创,转载请保留文章出处。