Be the first user to complete this post

  • 0
 Add to List
Medium

452. Activity Selection Problem

Objective: The activity selection problem is a combinatorial optimization problem concerning the selection of non-conflicting activities to perform within a given time frame, given a set of activities each marked by a start time (si) and finish time (fi). The problem is to select the maximum number of activities that can be performed by a single person or machine, assuming that a person can only work on a single activity at a time. 

Non-Conflicting activities: Let's consider there are N activities and for each activity, there is a start s time and end time f for that activity. Two activities i and j are said to be non-conflicting if si ≥ fj or sj ≥ fi.

Example:

Given Activities: [[1, 3], [2, 5], [0, 7], [6, 8], [9, 11], [10, 12]]
Selected Activities:
[1, 3] [6, 8] [9, 11]

Given Activities: [[1, 3], [2, 5]]
Selected Activities:
[1, 3]

Given Activities: [[0, 7], [1, 3], [4, 5]]
Selected Activities:
[1, 3] [4, 5]

Algorithm: Greedy

  1. Sort all the activities according to their end time.
  2. Select the first activity and note the end time, call it as current_end.
  3. Now iterate through the rest of the activities. For each current_activity
    1. If start time of current_activity > current_end 
      1. Select current_activity.
      2. Update current_end = end time of current_activity.
    2. Else
      1. Ignore the current_acitvity.

Time Complexity: O(nlogn)

 

Output:

Given Activities: [[1, 3], [2, 5], [0, 7], [6, 8], [9, 11], [10, 12]]
Selected Activities: [[1, 3], [6, 8], [9, 11]]

Reference: https://en.wikipedia.org/wiki/Activity_selection_problem

Related Problems: