Greedy Activity Selector Java Source Code

24May/100

Greedy Activity Selector Java Source Code

Activity Selector is problem to choose which event will be choosen to get maximum number of event for using the resources (time). Each event has start time and finish time. Two or more event cannot use the resource at the same time.

And here is the recursive and iterative solution pseudocode based on Introduction to Algorithm, 2nd edition

RECURSIVE-ACTIVITY-SELECTOR(s, f, i, j)
1 m ← i + 1
2 while m  < j and sm < fi ▹ Find the first activity in Sij.
3     do m ← m + 1
4 if m < j
5    then return {am} ∪ RECURSIVE-ACTIVITY-SELECTOR(s, f, m, j)
6    else return Ø

GREEDY-ACTIVITY-SELECTOR(s, f)
1 n ← length[s]
2 A ← {a1}
3 i ← 1
4 for m ← 2 to n
5      do if sm ≥ fi
6            then A ← A ∪ {am}
7                 i ← m
8 return A

How about the implementation on java source code.... Let's check this out

    public static String recursiveActivitySelector(int[] s, int[] f, int i, int j){
        int m = i + 1;
        while (m < j && s[m] < f[i]){
            m = m + 1;
        }
        if (m < j){
            return Integer.toString(m+1) +" "+ recursiveActivitySelector(s, f, m, j);
        }
        else return "";
    }

And the iterative solution is....

    public static String iterativeActivitySelector(int[] s, int[] f){
        String a = "1";
        int i = 0;
        int n = s.length;

        for (int m=1;m<n;m++){
            if (s[m] >= f[i]){
                a = a + " " + (m+1);
                i = m;
            }
        }
        return a;
    }

Okay, that's it... Try and keep going with your work