问题
选出最大的互相兼容的活动集合
| $a_i$(活动) | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 |
| $s_i$(开始时间) | 1 | 3 | 0 | 5 | 3 | 5 | 6 | 8 | 8 | 2 | 12 |
| $f_i$(结束时间) | 4 | 5 | 6 | 7 | 9 | 9 | 10 | 11 | 12 | 14 | 16 |
code
public class _0402MaxActivitiesCombination {
@Test
public void maxActivitiesCombination_test() {
int[] s = {1,3,0,5,3,5,6,8,8,2,12};
int[] f = {4,5,6,7,9,9,10,11,12,14,16};
boolean[] a = new boolean[s.length];
this.printMaxActivitiesCombination(s,f,a);
}
private void printMaxActivitiesCombination(int[] s, int[] f, boolean[] a) {
int j = 0;
int count = 1;
a[0] = true;
for (int i = 1; i < s.length; i++) {
if(s[i] >= f[j]){
a[i] = true;
count ++;
j = i;
}
}
System.out.println(count);
}
}
图解
