• At each decision point, makes choice that seems best at the moment
• This heuristic strategy does not always produce an optimal solution
• Steps
  • Determine the optimal substructure of the problem
  • Develop a recursive solution, using dynamic programming
  • Show that is we make the greedy choice, then only one subproblem remains
  • Prove that it is always safe to make the greedy choice
  • Develop a recursive algorithm that implements the greedy strategy
  • Convert the recursive algorithm to an iterative algorithm
• Greedy Steps
  • Cast the optimization problem as one in which we make a choice and are left with one subproblem to solve
  • Prove that there is always an optimal solution to the original problem that makes the greedy choice, so that the greedy choice is always safe
  • Demonstrate optimal substructure by showing that, having made the greedy choice, what remains is a subproblem with the property that if we combine an optimal solution to the subproblem with the greedy choice we have made, we arrive at an optimal solution to the original problem
• Greedy-choice property
  • Greedy algorithm makes its first choice before solving any subproblems; a dynamic programming solves the subproblems before making the first choice
  • Greedy progresses in a top-down fashion; a dynamic programming progresses in a bottom-up fashion

• Select a maximum-size subset of mutually compatible activities

public class P
{
	private int s, f;

	public P(int s, int f)
	{
		this.s = s;
		this.f = f;
	}

	public int getS() {return s;}
	public int getF() {return f;}
}
			

//Top-Down
import java.util.*;
import javafx.util.*;

public class A
{
	public static int firstEnd(P [] array, int start, int current)
	{
		if(start >= current)
			return start-1;

		int i;
		for(i = current-1; i >= start; i--)
		{
			if(array[i].getF() <g array[current].getS())
				return i;
		}
		return i;
	}

	public static int secondStart(P [] array, int current, int end)
	{
		if(current >= end)
			return end+1;

		int i;
		for(i = current+1; i <= end; i++)
		{
			if(array[i].getS() > array[current].getF())
				return i;
		}
		return i;
	}

	public static int activities(P [] array, int start, int end)
	{
		if(start > end)
			return 0;

		int max = Integer.MIN_VALUE;

		for(int i = start; i <= end; i++)
		{
			int first = firstEnd(array, start, i);
			int second = secondStart(array, i, end);
			max = Math.max(max, activities(array, start, first)+activities(array, second, end)+1);
		}

		return max;
	}

	public static void main(String args[])
	{
		P [] array = new P[11];

		array[0] = new P(1, 4);
		array[1] = new P(3, 5);
		array[2] = new P(0, 6);
		array[3] = new P(5, 7);
		array[4] = new P(3, 9);
		array[5] = new P(5, 9);
		array[6] = new P(6, 10);
		array[7] = new P(8, 11);
		array[8] = new P(8, 12);
		array[9] = new P(2, 14);
		array[10] = new P(12, 16);

		System.out.println(activities(array, 0, array.length-1));
	}
}
			

//Top-Down with Memorization
import java.util.*;
import javafx.util.*;

public class A
{
	public static int firstEnd(P [] array, int start, int current)
	{
		if(start >= current)
			return start-1;

		int i;
		for(i = current-1; i >= start; i--)
		{
			if(array[i].getF() < array[current].getS())
				return i;
		}
		return i;
	}

	public static int secondStart(P [] array, int current, int end)
	{
		if(current >= end)
			return end+1;

		int i;
		for(i = current+1; i <= end; i++)
		{
			if(array[i].getS() > array[current].getF())
				return i;
		}
		return i;
	}

	public static int activities(P [] array, int start, int end, int [][] c)
	{
		if(start > end)
			return 0;

		if(c[start][end] > 0)
			return c[start][end];

		int max = Integer.MIN_VALUE;

		for(int i = start; i <= end; i++)
		{
			int first = firstEnd(array, start, i);
			int second = secondStart(array, i, end);
			max = Math.max(max, activities(array, start, first, c)+activities(array, second, end, c)+1);
		}

		c[start][end] = max;
		return max;
	}

	public static void main(String args[])
	{
		P [] array = new P[11];

		array[0] = new P(1, 4);
		array[1] = new P(3, 5);
		array[2] = new P(0, 6);
		array[3] = new P(5, 7);
		array[4] = new P(3, 9);
		array[5] = new P(5, 9);
		array[6] = new P(6, 10);
		array[7] = new P(8, 11);
		array[8] = new P(8, 12);
		array[9] = new P(2, 14);
		array[10] = new P(12, 16);

		int [][] c = new int[11][11];

		System.out.println(activities(array, 0, array.length-1,c));
	}
}
			

//Bottom-Up
import java.util.*;
import javafx.util.*;

public class A
{
	public static int firstEnd(P [] array, int start, int current)
	{
		if(start >= current)
			return start-1;

		int i;
		for(i = current-1; i >= start; i--)
		{
			if(array[i].getF() < array[current].getS())
				return i;
		}
		return i;
	}

	public static int secondStart(P [] array, int current, int end)
	{
		if(current >= end)
			return end+1;

		int i;
		for(i = current+1; i <= end; i++)
		{
			if(array[i].getS() > array[current].getF())
				return i;
		}
		return i;
	}

	public static int activities(P [] array, int start, int end)
	{
		int [][] c = new int[array.length][array.length];


		for(int row = 0; row < array.length; row++)
		{
			for(int column = 0; column < array.length; column++)
			{
				if(row > column)
					continue;
				int max = Integer.MIN_VALUE;
				for(int i = row; i <= column; i++)
				{
					int first = firstEnd(array, row, i);
					int second = secondStart(array, i, column);
					int firstPart, secondPart;
					if(row > first)
						firstPart = 0;
					else
						firstPart = c[row][first];
					if(second > column)
						secondPart = 0;
					else
						secondPart = c[second][column];
					max = Math.max(max, firstPart+secondPart+1);
				}
				c[row][column] = max;
			}
		}

		return c[start][end];
	}

	public static void main(String args[])
	{
		P [] array = new P[11];

		array[0] = new P(1, 4);
		array[1] = new P(3, 5);
		array[2] = new P(0, 6);
		array[3] = new P(5, 7);
		array[4] = new P(3, 9);
		array[5] = new P(5, 9);
		array[6] = new P(6, 10);
		array[7] = new P(8, 11);
		array[8] = new P(8, 12);
		array[9] = new P(2, 14);
		array[10] = new P(12, 16);

		System.out.println(activities(array, 0, array.length-1));
	}
}
			

//Bottom-Up with Constructing Subset
/** An activity-selection problem in CLRS Ch16.1
 * @author Lin Chen
 * @since 11.14.2017
 */
import java.util.*;
import javafx.util.*;

public class A
{
	/** Get the valid activity before the current activity
	 * @param array array of activities
	 * @param start index of start activity
	 * @param current index of current activity
	 * @return {@code int}, index of valid activity before current activity
	 */
	public static int firstEnd(P [] array, int start, int current)
	{
		if(start >= current)
			return start-1;

		int i;
		for(i = current-1; i >= start; i--)
		{
			if(array[i].getF() < array[current].getS())
				return i;
		}
		return i;
	}

	/** Get the valid activity after the current activity
	 * @param array array of activities
	 * @param current index of current activity
	 * @param end index of end activity
	 * @return {@code int}, index of valid activity after current activity
	 */
	public static int secondStart(P [] array, int current, int end)
	{
		if(current >= end)
			return end+1;

		int i;
		for(i = current+1; i <= end; i++)
		{
			if(array[i].getS() > array[current].getF())
				return i;
		}
		return i;
	}

	/** Bottom-up with constructing set consisting of mutually compatible activities
	 * @param array array of activities
	 * @param start index of start activity
	 * @param end index of end activity
	 * @param s array to save a[k] to maximum c[start, end]
	 * @return {@code int}, number of available mutually compatible activities
	 */
	public static int activities(P [] array, int start, int end, int [][] s)
	{
		int [][] c = new int[array.length][array.length];

		for(int row = 0; row < array.length; row++)
		{
			for(int column = 0; column < array.length; column++)
			{
				if(row > column)
					continue;
				int max = Integer.MIN_VALUE;
				for(int i = row; i <= column; i++)
				{
					int first = firstEnd(array, row, i);
					int second = secondStart(array, i, column);
					int firstPart, secondPart;
					if(row > first)
						firstPart = 0;
					else
						firstPart = c[row][first];
					if(second > column)
						secondPart = 0;
					else
						secondPart = c[second][column];
					if(max < firstPart+secondPart+1)
					{
						max = firstPart+secondPart+1;
						s[row][column] = i;
					}
				}
				c[row][column] = max;
			}
		}

		return c[start][end];
	}

	/** print the maximum subset
	 * @param array array of activities
	 * @param s array to save a[k] to maximum c[start, end]
	 * @param start index of start activity
	 * @param end index of end activity
	 */
	public static void printActivity(P [] array, int [][] s, int start, int end)
	{
		if(start > end)
			return;
		printActivity(array, s, start, firstEnd(array, start, s[start][end]));
		System.out.printf("%5d", s[start][end]);
		printActivity(array, s, secondStart(array, s[start][end], end), end);
	}

	/** print array
	 * @param array integer array
	 */
	public static void display(int [][] array)
	{
		for(int i = 0; i < array.length; i++)
		{
			for(int j = 0; j < array[0].length; j++)
			{
				System.out.printf("%5d", array[i][j]);
			}
			System.out.println();
		}
	}

	public static void main(String args[])
	{
		P [] array = new P[11];

		array[0] = new P(1, 4);
		array[1] = new P(3, 5);
		array[2] = new P(0, 6);
		array[3] = new P(5, 7);
		array[4] = new P(3, 9);
		array[5] = new P(5, 9);
		array[6] = new P(6, 10);
		array[7] = new P(8, 11);
		array[8] = new P(8, 12);
		array[9] = new P(2, 14);
		array[10] = new P(12, 16);

		int [][] s = new int[array.length][array.length];

		System.out.println(activities(array, 0, array.length-1, s));

		//display(s);

		printActivity(array, s, 0, array.length-1);
		System.out.println();
	}
}
			

//Greedy Algorithm, O(n)
/** An activity-selection problem in CLRS Ch16.1
 * @author Lin Chen
 * @since 11.14.2017
 */
import java.util.*;
import javafx.util.*;

public class A
{
	/** Bottom-up with constructing set consisting of mutually compatible activities
	 * @param array array of activities
	 * @param start index of current activity
	 * @param end index of end activity
	 * @param records store activities
	 */
	public static void activitySelector(P [] array, int current, int end, ArrayList<Integer> records)
	{
		int m = current + 1;

		while(m <= end && array[m].getS() < array[current].getF())
			m++;

		if(m <= end)
		{
			records.add(m);
			activitySelector(array, m, end, records);
		}
	}

	public static void main(String args[])
	{
		P [] array = new P[11];

		//sort activities by increasing finish time
		array[0] = new P(1, 4);
		array[1] = new P(3, 5);
		array[2] = new P(0, 6);
		array[3] = new P(5, 7);
		array[4] = new P(3, 9);
		array[5] = new P(5, 9);
		array[6] = new P(6, 10);
		array[7] = new P(8, 11);
		array[8] = new P(8, 12);
		array[9] = new P(2, 14);
		array[10] = new P(12, 16);

		ArrayList<Integer> records = new ArrayList<Integer>();

		records.add(0);
		activitySelector(array, 0, array.length-1, records);

		for(Integer e : records)
			System.out.printf("%5d", e);
		System.out.println();
	}
}
			

//Iterative Greedy Algorithm, O(n)
/** An activity-selection problem in CLRS Ch16.1
 * @author Lin Chen
 * @since 11.14.2017
 */
import java.util.*;
import javafx.util.*;

public class A
{
	/** Bottom-up with constructing set consisting of mutually compatible activities
	 * @param array array of activities
	 * @param start index of current activity
	 * @param end index of end activity
	 * @param records store activities
	 */
	public static ArrayList<Integer> activitySelector(P [] array)
	{
		ArrayList<Integer> records = new ArrayList<Integer>();

		records.add(0);

		int n = array.length;
		int k = 0;

		for(int m = 2; m < n; m++)
		{
			if(array[m].getS() >= array[k].getF())
			{
				records.add(m);
				k = m;
			}
		}

		return records;
	}

	public static void main(String args[])
	{
		P [] array = new P[11];

		//sort activities by increasing finish time
		array[0] = new P(1, 4);
		array[1] = new P(3, 5);
		array[2] = new P(0, 6);
		array[3] = new P(5, 7);
		array[4] = new P(3, 9);
		array[5] = new P(5, 9);
		array[6] = new P(6, 10);
		array[7] = new P(8, 11);
		array[8] = new P(8, 12);
		array[9] = new P(2, 14);
		array[10] = new P(12, 16);

		ArrayList<Integer> records = activitySelector(array);

		for(Integer e : records)
			System.out.printf("%5d", e);
		System.out.println();
	}
}
			

• CLRS Chapter 16.1