Question

Give an example that shows the greedy algorithm for activity selection that picks the activity with the smallest start time first (and continues in that fashion) does not solve the activity selection problems correctly.

Please show your work! I will rate quality answers. Thank you.

Answer 1

Consider the following 3 activities sorted by

by finish time.

     start[] = {10, 12, 20};

     finish[] = {20, 25, 30};

A person can perform at most two activities. The

maximum set of activities that can be executed

is {0, 2} [ These are indexes in start[] and

finish[] ]

import java.util.*;

import java.lang.*;

import java.io.*;

class ActivitySelection

{

    public static void printMaxActivities(int s[], int f[], int n)

    {

    int i, j;

     

    System.out.print("Following activities are selected : \n");

    i = 0;

    System.out.print(i+" ");

    for (j = 1; j < n; j++)

    {

         if (s[j] >= f[i])

         {

              System.out.print(j+" ");

              i = j;

          }

     }

    }

    public static void main(String[] args)

    {

    int s[] = {1, 3, 0, 5, 8, 5};

    int f[] = {2, 4, 6, 7, 9, 9};

    int n = s.length;

    printMaxActivities(s, f, n);

    }

     }