Activity-Selection Problem

The activity selection problem involves selecting the maximum number of activities that can be performed by a single person or resource, given a collection of activities with start and finish times.

Some sample pseudocode:

Input: Array of activities with start and finish times

Sort activities by finish time

Initialize selected activity list to first activity

For each remaining activity:
  If activity start time >= finish time of last selected:
    Add activity to selected list

Return selected list

The key steps are:

  1. Sort activities by finish time
  2. Select first activity to initialize selected list
  3. Iterate through remaining activities:
    • If activity start time is after last selected finish, select activity
  4. Return final selected list

This greedy approach ensures we pick the maximum number of non-conflicting activities sorted by earliest finish time.

Some example code:

Java:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Activity {
  int start, finish;
}

// Sort activities by finish time  
Collections.sort(activities, (a, b) -> a.finish - b.finish);

List<Activity> selected = new ArrayList<>();
selected.add(activities.get(0));

for(int i=1; i<activities.size(); i++) {
  if(activities.get(i).start >= selected.get(selected.size()-1).finish) {
    selected.add(activities.get(i)); 
  }
}

Python:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Activity:
  def __init__(self, start, finish):
    self.start = start
    self.finish = finish

# Sort activities by finish time
activities.sort(key=lambda x: x.finish)  

selected = [activities[0]]

for activity in activities[1:]:
  if activity.start >= selected[-1].finish:
    selected.append(activity)

This activity selection algorithm ensures maximum activities are selected without conflicts. It has O(n log n) time complexity.

The Activity-Selection Problem deals with selecting the maximum number of activities that don’t overlap with each other. The goal is to pick the most number of activities that can be performed by a single person, given a start time and finish time for each activity.

Algorithm

  1. Sort Activities: Sort all activities based on their finish time.
  2. Select Initial Activity: The first activity always gets selected.
  3. Iterate and Select: For each following activity, if the start time is greater than or equal to the finish time of the previously selected, then select this activity.

Java Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

import java.util.Arrays;
import java.util.Comparator;

class Activity {
  int start, finish;
  // constructor and getters/setters
}

public class ActivitySelection {
  public static void activitySelection(Activity arr[]) {
    Arrays.sort(arr, Comparator.comparingInt(a -> a.finish));
    int n = arr.length;
    int i = 0;
    for (int j = 1; j < n; j++) {
      if (arr[j].start >= arr[i].finish) {
        System.out.println("Activity " + j + " is selected.");
        i = j;
      }
    }
  }
}

C++ Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

#include <iostream>
#include <algorithm>
#include <vector>

struct Activity {
  int start, finish;
};

bool activityCompare(Activity s1, Activity s2) {
  return (s1.finish < s2.finish);
}

void activitySelection(std::vector<Activity> &activities) {
  std::sort(activities.begin(), activities.end(), activityCompare);
  int i = 0;
  for (int j = 1; j < activities.size(); j++) {
    if (activities[j].start >= activities[i].finish) {
      std::cout << "Activity " << j << " is selected.\n";
      i = j;
    }
  }
}

int main() {
  // Create vector of activities and call activitySelection()
}

Python Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

def activity_selection(activities):
    activities.sort(key=lambda x: x[1])
    i = 0
    for j in range(1, len(activities)):
        if activities[j][0] >= activities[i][1]:
            print(f"Activity {j} is selected.")
            i = j

# Usage
activities = [(1, 2), (3, 4), (0, 6), (5, 7), (8, 9), (5, 9)]
activity_selection(activities)

The algorithm has a time complexity of (O(N \log N)) due to sorting, where (N) is the number of activities. After sorting, the activity selection takes (O(N)) time.