Posts Activity Selection (geeksforgeeks - SDE Sheet)
Post
Cancel

Activity Selection (geeksforgeeks - SDE Sheet)

PROBLEM DESCRIPTION

Given N activities with their start and finish day given in array start[ ] and end[ ]. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a given day. Note : Duration of the activity includes both starting and ending day.

geeksforgeeks

SOLUTION

This is similar to: N Meetings in One Room

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
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution
{

    public static int activitySelection(int start[], int end[], int n)
    {
        // 2D array to store start and end times of activities
        int[][] activity = new int[n][2];

        for(int i = 0; i < n; i++){
            activity[i] = new int[]{start[i], end[i]};
        }

        // Sort activities based on their end times
        Arrays.sort(activity, (a, b) -> a[1] - b[1]);

        // 1 activity can be done always (n > 0)
        int count = 1;

        // End time of the first activity
        int prevEnd = activity[0][1];

        // Iterate through other activities
        for(int i = 1; i < n; i++){

            // If the start time of the current activity is greater than the end time
            // of the last selected activity, we can select it
            if(activity[i][0] > prevEnd){

                count++;

                // Update the end time to the current activity's end time
                prevEnd = activity[i][1];

            }
        }

        return count;
    }
}
This post is licensed under CC BY 4.0 by the author.