Full Example — Activity Selection Problem

An activity-selection is the problem of scheduling a resource among several competing activity.

/*
 * A greedy algorithm for activity selection
 * 
 * 
 * Author: Pedro Garcia Freitas [sawp@sawp.com.br>]
 * Date: Aug, 2011
 *
 * [Ref] Cormen, Thomas H. "Introduction to Algorithms" -- 3rd ed.
 */
import scala.collection.mutable.ListBuffer


class Activity(val name: String, val start: Int, val finish: Int) {
  override def toString = 
    name + "[" + start + "," + finish + "]"
}

def greedy_activity_selector(ac: List[Activity]): List[Activity] = {
  var k = 0
  val A = new ListBuffer[Activity]
  A += ac(0)
  for (m < - 1 until ac.length) {
    if (ac(m).start >= ac(k).finish) {
      A += ac(m)
      k = m
    }
  }
  A.toList
}

val activities = List(
  new Activity("Calculus", 1, 5),
  new Activity("Numerical Analysis", 2, 4),
  new Activity("Introduction to Computational Methods", 2, 7),
  new Activity("Physics", 4, 6),
  new Activity("Numerical Methods for Physics", 5, 6),
  new Activity("Algorithms 1", 6, 7),
  new Activity("Operating Systems", 7, 9)
)

println("\nActivities: " + activities)

println("\n\nPossible Distribution of activities: " +
  greedy_activity_selector(activities))