Activity Selection Problem in Kotlin

by

The activity selection problem is a classic optimization problem that involves selecting the maximum number of mutually compatible activities from a given set of activities, where each activity has a start time and an end time. The goal is to select the maximum number of activities such that no two selected activities overlap.

To solve this problem, we can use a greedy approach that selects the activity with the earliest end time first, and then selects the next activity with the earliest end time that does not overlap with the previously selected activity. This process continues until no more mutually compatible activities can be selected.

Here’s an example:

Suppose we have the following set of activities, each represented by its start and end times:

Activities:
-------------------------------------
|  Start Time |  End Time | Activity |
-------------------------------------
|     1            |     3           |     A      |
|     2            |     5           |     B      |
|     3            |     8           |     C      |
|     4            |     9           |     D      |
|     5            |     10         |     E       |
|     6            |     11         |     F       |
|     7            |     12         |     G      |
|     8            |     13         |     H      |
|     9            |     14         |     I        |
|     10          |     15         |     J        |
--------------------------------------

Using the greedy approach described above, we can select the following activities:

  1. Select activity A, since it has the earliest end time.
  2. Activity B cannot be selected, because it overlaps with activity A.
  3. Select activity C, since it has the earliest end time that does not overlap with activity A.
  4. Activity D cannot be selected, because it overlaps with activity C.
  5. Select activity E, since it has the earliest end time that does not overlap with activity A or C.
  6. Activity F cannot be selected, because it overlaps with activity E.
  7. Select activity G, since it has the earliest end time that does not overlap with activity A, C, or E.
  8. Activity H cannot be selected, because it overlaps with activity G.
  9. Activity I cannot be selected, because it overlaps with activity G.
  10. Select activity J, since it has the earliest end time that does not overlap with activity A, C, E, or G.

Therefore, the maximum number of mutually compatible activities that can be selected is 5 (A, C, E, G, J).

Kotlin
fun selectActivities(activities: List<Activity>): List<Activity> {
    // Sort activities by end time in ascending order
    val sortedActivities = activities.sortedBy { it.end }

    // Select the first activity
    var selectedActivities = mutableListOf(sortedActivities.first())

    // Iterate over the remaining activities
    for (activity in sortedActivities.drop(1)) {
        // If the start time of the current activity is after the end time of the last selected activity,
        // then select the current activity
        if (activity.start >= selectedActivities.last().end) {
            selectedActivities.add(activity)
        }
    }

    return selectedActivities
}

The selectActivities function is used to solve the activity selection problem using a greedy approach. It takes a list of activities as input and returns a list of the maximum number of mutually compatible activities.

The first step in the function is to sort the list of activities by their end time in ascending order. This is done so that we can always select the activity with the earliest end time as our first choice.

Next, we initialize a list called selectedActivities that will store the selected activities. We start by selecting the first activity in the sorted list, since it has the earliest end time.

Then, we iterate over the remaining activities in the sorted list. For each activity, we check whether its start time is after the end time of the last selected activity. If it is, then we can select the current activity since it does not overlap with any of the previously selected activities. We add the current activity to the selectedActivities list.

We continue this process until we have iterated over all the activities in the sorted list. At the end, we return the selectedActivities list as the result.

In summary, the selectActivities function uses a greedy approach to solve the activity selection problem by always selecting the activity with the earliest end time and then choosing subsequent activities that do not overlap with previously selected activities.

Kotlin
data class Activity(val start: Int, val end: Int)

fun selectActivities(activities: List<Activity>): List<Activity> {
    // Sort activities by end time in ascending order
    val sortedActivities = activities.sortedBy { it.end }

    // Select the first activity
    var selectedActivities = mutableListOf(sortedActivities.first())

    // Iterate over the remaining activities
    for (activity in sortedActivities.drop(1)) {
        // If the start time of the current activity is after the end time of the last selected activity,
        // then select the current activity
        if (activity.start >= selectedActivities.last().end) {
            selectedActivities.add(activity)
        }
    }

    return selectedActivities
}
fun main() {
    val activities = listOf(
        Activity(1, 3),
        Activity(2, 5),
        Activity(3, 8),
        Activity(4, 9),
        Activity(5, 10),
        Activity(6, 11),
        Activity(7, 12),
        Activity(8, 13),
        Activity(9, 14),
        Activity(10, 15)
    )

    val selectedActivities = selectActivities(activities)

    println("Selected activities:")
    selectedActivities.forEach {
        println("Activity ${it.start}-${it.end}")
    }
}

Output :

Selected activities:
Activity 1-3
Activity 3-8
Activity 8-13
Activity 13-15

Leave a Comment