[LanQiao]区间选点问题

11
2019/08

# [LanQiao]区间选点问题

### 原始问题

#### 分析

t 排序

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;
}

}
}

百度未收录

Last modification：August 12th, 2019 at 05:12 pm