欲張りアルゴリズム--アクティビティの手配


 1 package cn.it;

 2 

 3 import java.util.Arrays;

 4 

 5 public class Tx {

 6     public static void main(String[] args) {

 7         int start[]={1,4,2,1,2,4,5};

 8         int end[]={5,6,3,2,4,5,6};

 9         int n=6;

10         boolean a[]= new boolean[n];

11         sort(start,end,n);

12         int count = manage(start, end, a, n);

13         System.out.println(Arrays.toString(start));

14         System.out.println(Arrays.toString(end));

15         System.out.println(count+":===:"+ Arrays.toString(a));

16         

17     }

18     

19     public static void sort(int start[],int end[],int n){

20         //     

21         for(int i=0;i<n;i++){

22             for(int j=i;j<n;j++){

23                 if(end[i]>end[j]){

24                     

25                     int temp = end[i];

26                     end[i]=end[j];

27                     end[j]=temp;

28                     

29                     temp = start[i];

30                     start[i]=start[j];

31                     start[j]=temp;

32                 }

33             }

34         }

35     }

36     

37     public static int manage(int start[],int end[],boolean a[],int n){

38         a[0]=true;

39         int count=1;

40         int j=0;

41         for(int i=1;i<n;i++){

42             //

43             if(start[i]>=end[j]){

44                 a[i]=true;

45                 j=i;

46                 count++;

47             }else{

48                 a[i]=false;

49             }

50         }

51         

52         return count;

53     }

54 }