many activities will use the same place, every activity ai has its' start time si and finish time fi.let the number of activities to be as many as possible.
1. dynamic programming
use ak be a knife to cut the set activities into two parts and recursive to find the max subset
c[i,j](star after ai finish and finish before aj star) = max {1+c[i,k] + c[k,j]} or 0(haven't ak);
2.greedy programming
let ai ranked by their finish time. earlier finish time ranked front than the later.
then choose the activities by its finish time, keep they are not contradictory.
1 public class activity_select { 2 int[] s = {1,3,0,5,3,5,6,8,8,2,12}; 3 int[] f = {4,5,6,7,9,9,10,11,12,14,16}; 4 private static class activity{ 5 private int sta ; 6 private int fin ; 7 public activity(){ 8 sta = 0; 9 fin = 0; 10 } 11 } 12 13 public activity[] select(){ 14 activity[] act = new activity[s.length]; 15 for(int i = 0;i<s.length;i++){ //initial 16 act[i] = new activity(); 17 act[i].sta = s[i]; 18 act[i].fin = f[i]; 19 } 20 for(int i = 0;i<s.length;i++){ //insert sort from early fin to later fin 21 for(int j = i;j < s.length;j++){ 22 if(act[i].fin > act[j].fin){ 23 int testa = act[j].sta; 24 int tefin = act[j].fin; 25 act[j].sta = act[i].sta; 26 act[j].fin = act[i].fin; 27 act[i].fin = tefin; 28 act[i].sta = testa; 29 } 30 } 31 } 32 activity[] res = new activity[s.length]; 33 res[0] = act[0]; 34 int j = 0; 35 for(int i = 0;i < s.length -1;i++){ 36 if(act[i+1].sta > res[j].fin){ 37 res[++j] = act[i + 1]; 38 } 39 } 40 activity[] res1 = new activity[j+1]; 41 for(int i = 0;i <=j;i++){ 42 res1[i] = res[i]; 43 } 44 return res1; 45 } 46 47 48 49 public static void main(String[] args){ 50 activity_select ac = new activity_select(); 51 activity[] a = ac.select(); 52 int n = a.length; 53 for(int i = 0;i < n;i++){ 54 System.out.println(a[i].sta + " " +a[i].fin); 55 } 56 } 57 58 59 }