activity selection - asked in facebook, ms , flipkart. + explaination

import java.util.*;

public class Main

{

public static void main(String[] args) { // O(n)

int start[] = {1, 3, 0, 5, 8, 5};

int end[] = {2, 4, 6, 7, 9, 9};

// end time basis sorted

int maxAct = 0;

ArrayList<Integer> ans = new ArrayList<>();

//sorting 

int activities[][] = new int[start.length][3];

for(int i=0; i<start.length; i++) {

    activities[i][0] = i;

    activities[i][1] = start[i];

    activities[i][2] = end[i];

}

// lambda function -> shortform

Arrays.sort(activities, Comparator.comparingDouble(o -> o[2]));

// 1st activity

maxAct = 1;

ans.add(activities[0][0]);

int lastEnd = activities[0][2];

for(int i=1; i<end.length; i++) {

    if(activities[i][1] >= lastEnd) {

        // activity select

        maxAct++;

        ans.add(activities[i][0]);

        lastEnd = activities[i][2];

    }

}

System.out.println("max activities = " + maxAct);

for(int i=0; i<ans.size(); i++) {

    System.out.print("A"+ans.get(i) + " ");

    

}

System.out.println();

}

}



EXPLAINATION:

This code is a classic implementation of the Activity Selection Problem using a "Greedy Algorithm" approach.

The Goal

Imagine you have a single meeting room and a list of requested meetings (activities), each with a start time and an end time. You want to select the maximum number of meetings possible without any of them overlapping.

The logic used here is: "Always pick the next activity that finishes the earliest."

---

Step-by-Step Explanation

1. The Input Data

Java

int start[] = {1, 3, 0, 5, 8, 5};
int end[] =   {2, 4, 6, 7, 9, 9};

These arrays represent 6 different activities. For example:

• Activity 0 starts at 1 and ends at 2.

• Activity 2 starts at 0 and ends at 6.

2. Preparing the Data Structure

The code creates a 2D array called activities to keep the data organized. This is necessary because we are about to sort the activities, and we don't want to lose track of which start time belongs to which original index.

Java

int activities[][] = new int[start.length][3];
// ... loop filling the array ...

The activities array stores data in 3 columns:

• Column 0: The original index (ID of the activity: 0, 1, 2...).

• Column 1: The Start time.

• Column 2: The End time.

3. Sorting ( The Crucial Step)

Java

Arrays.sort(activities, Comparator.comparingDouble(o -> o[2]));

This sorts the activities based on Column 2 (End Time).

• Why? By picking activities that finish early, you leave more time remaining for other activities. This is the "Greedy" part.

• The Lambda: o -> o[2] is a shortcut saying "Compare the rows based on the value at index 2."

After sorting, your list looks like this:

Original Index (ID)	Start	End	Status
A0	1	2	Finishes earliest
A1	3	4
A2	0	6
A3	5	7
A4	8	9
A5	5	9

4. The Selection Loop

Now, the code iterates through the sorted list to pick activities.

A. Pick the first one:

Java

maxAct = 1;
ans.add(activities[0][0]); 
int lastEnd = activities[0][2];

The first activity in the sorted list (A0) finishes earliest, so we always pick it.

• Current End Time (lastEnd): 2

B. Check the rest:

The loop checks every subsequent activity. The condition if(activities[i][1] >= lastEnd) checks: Does this activity start after the previous one finished?

1. Check A1 (3, 4):

   • Does it start (3) after the lastEnd (2)? Yes.

   • Action: Select it. Update lastEnd to 4.

2. Check A2 (0, 6):

   • Does it start (0) after the lastEnd (4)? No. (Overlap!)

   • Action: Skip it.

3. Check A3 (5, 7):

   • Does it start (5) after the lastEnd (4)? Yes.

   • Action: Select it. Update lastEnd to 7.

4. Check A4 (8, 9):

   • Does it start (8) after the lastEnd (7)? Yes.

   • Action: Select it. Update lastEnd to 9.

5. Check A5 (5, 9):

   • Does it start (5) after the lastEnd (9)? No.

   • Action: Skip it.

---

Complexity Note

The comment in your code // O(n) is technically incorrect for the whole program.

• Sorting takes $O(N \log N)$.

• The Loop takes $O(N)$.

• Total Time Complexity: $O(N \log N)$ (dominated by the sort).

Final Output

The code will print:

Plaintext

max activities = 4
A0 A1 A3 A4 

Would you like me to explain how the Lambda function syntax works in more detail, or help you convert this to a custom Class instead of a 2D array?