Greedy Algorithm
A activity-selection problem

  1. public class P
  2. {
  3. 	private int s, f;
  4.  
  5. 	public P(int s, int f)
  6. 	{
  7. 		this.s = s;
  8. 		this.f = f;
  9. 	}
  10.  
  11. 	public int getS() {return s;}
  12. 	public int getF() {return f;}
  13. }
  14. 			
  1. //Top-Down
  2. import java.util.*;
  3. import javafx.util.*;
  4.  
  5. public class A
  6. {
  7. 	public static int firstEnd(P [] array, int start, int current)
  8. 	{
  9. 		if(start >= current)
  10. 			return start-1;
  11.  
  12. 		int i;
  13. 		for(i = current-1; i >= start; i--)
  14. 		{
  15. 			if(array[i].getF() <g array[current].getS())
  16. 				return i;
  17. 		}
  18. 		return i;
  19. 	}
  20.  
  21. 	public static int secondStart(P [] array, int current, int end)
  22. 	{
  23. 		if(current >= end)
  24. 			return end+1;
  25.  
  26. 		int i;
  27. 		for(i = current+1; i <= end; i++)
  28. 		{
  29. 			if(array[i].getS() > array[current].getF())
  30. 				return i;
  31. 		}
  32. 		return i;
  33. 	}
  34.  
  35. 	public static int activities(P [] array, int start, int end)
  36. 	{
  37. 		if(start > end)
  38. 			return 0;
  39.  
  40. 		int max = Integer.MIN_VALUE;
  41.  
  42. 		for(int i = start; i <= end; i++)
  43. 		{
  44. 			int first = firstEnd(array, start, i);
  45. 			int second = secondStart(array, i, end);
  46. 			max = Math.max(max, activities(array, start, first)+activities(array, second, end)+1);
  47. 		}
  48.  
  49. 		return max;
  50. 	}
  51.  
  52. 	public static void main(String args[])
  53. 	{
  54. 		P [] array = new P[11];
  55.  
  56. 		array[0] = new P(1, 4);
  57. 		array[1] = new P(3, 5);
  58. 		array[2] = new P(0, 6);
  59. 		array[3] = new P(5, 7);
  60. 		array[4] = new P(3, 9);
  61. 		array[5] = new P(5, 9);
  62. 		array[6] = new P(6, 10);
  63. 		array[7] = new P(8, 11);
  64. 		array[8] = new P(8, 12);
  65. 		array[9] = new P(2, 14);
  66. 		array[10] = new P(12, 16);
  67.  
  68. 		System.out.println(activities(array, 0, array.length-1));
  69. 	}
  70. }
  71. 			
  1. //Top-Down with Memorization
  2. import java.util.*;
  3. import javafx.util.*;
  4.  
  5. public class A
  6. {
  7. 	public static int firstEnd(P [] array, int start, int current)
  8. 	{
  9. 		if(start >= current)
  10. 			return start-1;
  11.  
  12. 		int i;
  13. 		for(i = current-1; i >= start; i--)
  14. 		{
  15. 			if(array[i].getF() < array[current].getS())
  16. 				return i;
  17. 		}
  18. 		return i;
  19. 	}
  20.  
  21. 	public static int secondStart(P [] array, int current, int end)
  22. 	{
  23. 		if(current >= end)
  24. 			return end+1;
  25.  
  26. 		int i;
  27. 		for(i = current+1; i <= end; i++)
  28. 		{
  29. 			if(array[i].getS() > array[current].getF())
  30. 				return i;
  31. 		}
  32. 		return i;
  33. 	}
  34.  
  35. 	public static int activities(P [] array, int start, int end, int [][] c)
  36. 	{
  37. 		if(start > end)
  38. 			return 0;
  39.  
  40. 		if(c[start][end] > 0)
  41. 			return c[start][end];
  42.  
  43. 		int max = Integer.MIN_VALUE;
  44.  
  45. 		for(int i = start; i <= end; i++)
  46. 		{
  47. 			int first = firstEnd(array, start, i);
  48. 			int second = secondStart(array, i, end);
  49. 			max = Math.max(max, activities(array, start, first, c)+activities(array, second, end, c)+1);
  50. 		}
  51.  
  52. 		c[start][end] = max;
  53. 		return max;
  54. 	}
  55.  
  56. 	public static void main(String args[])
  57. 	{
  58. 		P [] array = new P[11];
  59.  
  60. 		array[0] = new P(1, 4);
  61. 		array[1] = new P(3, 5);
  62. 		array[2] = new P(0, 6);
  63. 		array[3] = new P(5, 7);
  64. 		array[4] = new P(3, 9);
  65. 		array[5] = new P(5, 9);
  66. 		array[6] = new P(6, 10);
  67. 		array[7] = new P(8, 11);
  68. 		array[8] = new P(8, 12);
  69. 		array[9] = new P(2, 14);
  70. 		array[10] = new P(12, 16);
  71.  
  72. 		int [][] c = new int[11][11];
  73.  
  74. 		System.out.println(activities(array, 0, array.length-1,c));
  75. 	}
  76. }
  77. 			
  1. //Bottom-Up
  2. import java.util.*;
  3. import javafx.util.*;
  4.  
  5. public class A
  6. {
  7. 	public static int firstEnd(P [] array, int start, int current)
  8. 	{
  9. 		if(start >= current)
  10. 			return start-1;
  11.  
  12. 		int i;
  13. 		for(i = current-1; i >= start; i--)
  14. 		{
  15. 			if(array[i].getF() < array[current].getS())
  16. 				return i;
  17. 		}
  18. 		return i;
  19. 	}
  20.  
  21. 	public static int secondStart(P [] array, int current, int end)
  22. 	{
  23. 		if(current >= end)
  24. 			return end+1;
  25.  
  26. 		int i;
  27. 		for(i = current+1; i <= end; i++)
  28. 		{
  29. 			if(array[i].getS() > array[current].getF())
  30. 				return i;
  31. 		}
  32. 		return i;
  33. 	}
  34.  
  35. 	public static int activities(P [] array, int start, int end)
  36. 	{
  37. 		int [][] c = new int[array.length][array.length];
  38.  
  39.  
  40. 		for(int row = 0; row < array.length; row++)
  41. 		{
  42. 			for(int column = 0; column < array.length; column++)
  43. 			{
  44. 				if(row > column)
  45. 					continue;
  46. 				int max = Integer.MIN_VALUE;
  47. 				for(int i = row; i <= column; i++)
  48. 				{
  49. 					int first = firstEnd(array, row, i);
  50. 					int second = secondStart(array, i, column);
  51. 					int firstPart, secondPart;
  52. 					if(row > first)
  53. 						firstPart = 0;
  54. 					else
  55. 						firstPart = c[row][first];
  56. 					if(second > column)
  57. 						secondPart = 0;
  58. 					else
  59. 						secondPart = c[second][column];
  60. 					max = Math.max(max, firstPart+secondPart+1);
  61. 				}
  62. 				c[row][column] = max;
  63. 			}
  64. 		}
  65.  
  66. 		return c[start][end];
  67. 	}
  68.  
  69. 	public static void main(String args[])
  70. 	{
  71. 		P [] array = new P[11];
  72.  
  73. 		array[0] = new P(1, 4);
  74. 		array[1] = new P(3, 5);
  75. 		array[2] = new P(0, 6);
  76. 		array[3] = new P(5, 7);
  77. 		array[4] = new P(3, 9);
  78. 		array[5] = new P(5, 9);
  79. 		array[6] = new P(6, 10);
  80. 		array[7] = new P(8, 11);
  81. 		array[8] = new P(8, 12);
  82. 		array[9] = new P(2, 14);
  83. 		array[10] = new P(12, 16);
  84.  
  85. 		System.out.println(activities(array, 0, array.length-1));
  86. 	}
  87. }
  88. 			
  1. //Bottom-Up with Constructing Subset
  2. /** An activity-selection problem in CLRS Ch16.1
  3.  * @author Lin Chen
  4.  * @since 11.14.2017
  5.  */
  6. import java.util.*;
  7. import javafx.util.*;
  8.  
  9. public class A
  10. {
  11. 	/** Get the valid activity before the current activity
  12. 	 * @param array array of activities
  13. 	 * @param start index of start activity
  14. 	 * @param current index of current activity
  15. 	 * @return {@code int}, index of valid activity before current activity
  16. 	 */
  17. 	public static int firstEnd(P [] array, int start, int current)
  18. 	{
  19. 		if(start >= current)
  20. 			return start-1;
  21.  
  22. 		int i;
  23. 		for(i = current-1; i >= start; i--)
  24. 		{
  25. 			if(array[i].getF() < array[current].getS())
  26. 				return i;
  27. 		}
  28. 		return i;
  29. 	}
  30.  
  31. 	/** Get the valid activity after the current activity
  32. 	 * @param array array of activities
  33. 	 * @param current index of current activity
  34. 	 * @param end index of end activity
  35. 	 * @return {@code int}, index of valid activity after current activity
  36. 	 */
  37. 	public static int secondStart(P [] array, int current, int end)
  38. 	{
  39. 		if(current >= end)
  40. 			return end+1;
  41.  
  42. 		int i;
  43. 		for(i = current+1; i <= end; i++)
  44. 		{
  45. 			if(array[i].getS() > array[current].getF())
  46. 				return i;
  47. 		}
  48. 		return i;
  49. 	}
  50.  
  51. 	/** Bottom-up with constructing set consisting of mutually compatible activities
  52. 	 * @param array array of activities
  53. 	 * @param start index of start activity
  54. 	 * @param end index of end activity
  55. 	 * @param s array to save a[k] to maximum c[start, end]
  56. 	 * @return {@code int}, number of available mutually compatible activities
  57. 	 */
  58. 	public static int activities(P [] array, int start, int end, int [][] s)
  59. 	{
  60. 		int [][] c = new int[array.length][array.length];
  61.  
  62. 		for(int row = 0; row < array.length; row++)
  63. 		{
  64. 			for(int column = 0; column < array.length; column++)
  65. 			{
  66. 				if(row > column)
  67. 					continue;
  68. 				int max = Integer.MIN_VALUE;
  69. 				for(int i = row; i <= column; i++)
  70. 				{
  71. 					int first = firstEnd(array, row, i);
  72. 					int second = secondStart(array, i, column);
  73. 					int firstPart, secondPart;
  74. 					if(row > first)
  75. 						firstPart = 0;
  76. 					else
  77. 						firstPart = c[row][first];
  78. 					if(second > column)
  79. 						secondPart = 0;
  80. 					else
  81. 						secondPart = c[second][column];
  82. 					if(max < firstPart+secondPart+1)
  83. 					{
  84. 						max = firstPart+secondPart+1;
  85. 						s[row][column] = i;
  86. 					}
  87. 				}
  88. 				c[row][column] = max;
  89. 			}
  90. 		}
  91.  
  92. 		return c[start][end];
  93. 	}
  94.  
  95. 	/** print the maximum subset
  96. 	 * @param array array of activities
  97. 	 * @param s array to save a[k] to maximum c[start, end]
  98. 	 * @param start index of start activity
  99. 	 * @param end index of end activity
  100. 	 */
  101. 	public static void printActivity(P [] array, int [][] s, int start, int end)
  102. 	{
  103. 		if(start > end)
  104. 			return;
  105. 		printActivity(array, s, start, firstEnd(array, start, s[start][end]));
  106. 		System.out.printf("%5d", s[start][end]);
  107. 		printActivity(array, s, secondStart(array, s[start][end], end), end);
  108. 	}
  109.  
  110. 	/** print array
  111. 	 * @param array integer array
  112. 	 */
  113. 	public static void display(int [][] array)
  114. 	{
  115. 		for(int i = 0; i < array.length; i++)
  116. 		{
  117. 			for(int j = 0; j < array[0].length; j++)
  118. 			{
  119. 				System.out.printf("%5d", array[i][j]);
  120. 			}
  121. 			System.out.println();
  122. 		}
  123. 	}
  124.  
  125. 	public static void main(String args[])
  126. 	{
  127. 		P [] array = new P[11];
  128.  
  129. 		array[0] = new P(1, 4);
  130. 		array[1] = new P(3, 5);
  131. 		array[2] = new P(0, 6);
  132. 		array[3] = new P(5, 7);
  133. 		array[4] = new P(3, 9);
  134. 		array[5] = new P(5, 9);
  135. 		array[6] = new P(6, 10);
  136. 		array[7] = new P(8, 11);
  137. 		array[8] = new P(8, 12);
  138. 		array[9] = new P(2, 14);
  139. 		array[10] = new P(12, 16);
  140.  
  141. 		int [][] s = new int[array.length][array.length];
  142.  
  143. 		System.out.println(activities(array, 0, array.length-1, s));
  144.  
  145. 		//display(s);
  146.  
  147. 		printActivity(array, s, 0, array.length-1);
  148. 		System.out.println();
  149. 	}
  150. }
  151. 			
  1. //Greedy Algorithm, O(n)
  2. /** An activity-selection problem in CLRS Ch16.1
  3.  * @author Lin Chen
  4.  * @since 11.14.2017
  5.  */
  6. import java.util.*;
  7. import javafx.util.*;
  8.  
  9. public class A
  10. {
  11. 	/** Bottom-up with constructing set consisting of mutually compatible activities
  12. 	 * @param array array of activities
  13. 	 * @param start index of current activity
  14. 	 * @param end index of end activity
  15. 	 * @param records store activities
  16. 	 */
  17. 	public static void activitySelector(P [] array, int current, int end, ArrayList<Integer> records)
  18. 	{
  19. 		int m = current + 1;
  20.  
  21. 		while(m <= end && array[m].getS() < array[current].getF())
  22. 			m++;
  23.  
  24. 		if(m <= end)
  25. 		{
  26. 			records.add(m);
  27. 			activitySelector(array, m, end, records);
  28. 		}
  29. 	}
  30.  
  31. 	public static void main(String args[])
  32. 	{
  33. 		P [] array = new P[11];
  34.  
  35. 		//sort activities by increasing finish time
  36. 		array[0] = new P(1, 4);
  37. 		array[1] = new P(3, 5);
  38. 		array[2] = new P(0, 6);
  39. 		array[3] = new P(5, 7);
  40. 		array[4] = new P(3, 9);
  41. 		array[5] = new P(5, 9);
  42. 		array[6] = new P(6, 10);
  43. 		array[7] = new P(8, 11);
  44. 		array[8] = new P(8, 12);
  45. 		array[9] = new P(2, 14);
  46. 		array[10] = new P(12, 16);
  47.  
  48. 		ArrayList<Integer> records = new ArrayList<Integer>();
  49.  
  50. 		records.add(0);
  51. 		activitySelector(array, 0, array.length-1, records);
  52.  
  53. 		for(Integer e : records)
  54. 			System.out.printf("%5d", e);
  55. 		System.out.println();
  56. 	}
  57. }
  58. 			
  1. //Iterative Greedy Algorithm, O(n)
  2. /** An activity-selection problem in CLRS Ch16.1
  3.  * @author Lin Chen
  4.  * @since 11.14.2017
  5.  */
  6. import java.util.*;
  7. import javafx.util.*;
  8.  
  9. public class A
  10. {
  11. 	/** Bottom-up with constructing set consisting of mutually compatible activities
  12. 	 * @param array array of activities
  13. 	 * @param start index of current activity
  14. 	 * @param end index of end activity
  15. 	 * @param records store activities
  16. 	 */
  17. 	public static ArrayList<Integer> activitySelector(P [] array)
  18. 	{
  19. 		ArrayList<Integer> records = new ArrayList<Integer>();
  20.  
  21. 		records.add(0);
  22.  
  23. 		int n = array.length;
  24. 		int k = 0;
  25.  
  26. 		for(int m = 2; m < n; m++)
  27. 		{
  28. 			if(array[m].getS() >= array[k].getF())
  29. 			{
  30. 				records.add(m);
  31. 				k = m;
  32. 			}
  33. 		}
  34.  
  35. 		return records;
  36. 	}
  37.  
  38. 	public static void main(String args[])
  39. 	{
  40. 		P [] array = new P[11];
  41.  
  42. 		//sort activities by increasing finish time
  43. 		array[0] = new P(1, 4);
  44. 		array[1] = new P(3, 5);
  45. 		array[2] = new P(0, 6);
  46. 		array[3] = new P(5, 7);
  47. 		array[4] = new P(3, 9);
  48. 		array[5] = new P(5, 9);
  49. 		array[6] = new P(6, 10);
  50. 		array[7] = new P(8, 11);
  51. 		array[8] = new P(8, 12);
  52. 		array[9] = new P(2, 14);
  53. 		array[10] = new P(12, 16);
  54.  
  55. 		ArrayList<Integer> records = activitySelector(array);
  56.  
  57. 		for(Integer e : records)
  58. 			System.out.printf("%5d", e);
  59. 		System.out.println();
  60. 	}
  61. }
  62.
Huffman Codes

Reference