com.mhhe.clrs2e
Class RecursiveActivitySelector

java.lang.Object
  |
  +--com.mhhe.clrs2e.RecursiveActivitySelector

All Implemented Interfaces:

ActivitySelector

public class RecursiveActivitySelector

extends java.lang.Object

implements ActivitySelector

Implements the Recursive-Activity-Selector algorithm from page 376 of Introduction to Algorithms, Second edition.

Field Summary

private int

selected How many activities have been selected.

Constructor Summary

RecursiveActivitySelector()

Method Summary

private com.mhhe.clrs2e.SentinelDLL	recursiveActivitySelector(com.mhhe.clrs2e.Activity[] activities, int i, int n) Determines a maximum set of mutually compatible activities in a subset of the set of activities.
com.mhhe.clrs2e.Activity[]	selector(com.mhhe.clrs2e.Activity[] activities) Determines a maximum set of mutually compatible activities.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

selected

private int selected

How many activities have been selected.

Constructor Detail

RecursiveActivitySelector

public RecursiveActivitySelector()

Method Detail

selector

public com.mhhe.clrs2e.Activity[] selector(com.mhhe.clrs2e.Activity[] activities)

Determines a maximum set of mutually compatible activities.

Specified by:

selector in interface ActivitySelector

Parameters:

activities - Array of activities, assumed to be sorted by finish time. activities[0] must have a finish time of 0. All other activities must have nonnegative start times and positive finish times.

Returns:

An array consisting of a maximum set of mutually compatible activities from activities.

recursiveActivitySelector

private com.mhhe.clrs2e.SentinelDLL recursiveActivitySelector(com.mhhe.clrs2e.Activity[] activities,
                                                              int i,
                                                              int n)

Determines a maximum set of mutually compatible activities in a subset of the set of activities. Implements the Recursive-Activity-Selector procedure on page 376.

Parameters:

activities - Array of activities, assumed to be sorted by finish time. activities[0] must have a finish time of 0. All other activities must have nonnegative start times and positive finish times.

i - Index of the last activity selected.

n - Number of activities other than the 0th activity.

Returns:

A linked list of the selected activities.