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
These arrays represent 6 different activities. For example:
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.
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)
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:
The first activity in the sorted list (A0) finishes earliest, so we always pick it.
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?
Check A1 (3, 4):
Check A2 (0, 6):
Check A3 (5, 7):
Check A4 (8, 9):
Check A5 (5, 9):
Complexity Note
The comment in your code // O(n) is technically incorrect for the whole program.
Final Output
The code will print:
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?
