Coding · Greedy
Activity Selection
- Reported once
- Easy
- campus SDE-1
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
You are given the start and finish times of n unsorted activities, each starting before it finishes, and a single room, and you must pick as many activities as possible with no two overlapping; an activity may start at the moment another one finishes. Return how many you can pick. For starts [1,3,0,5,8,5] and finishes [2,4,6,7,9,10] the answer is 4, for example (1,2), (3,4), (5,7) and (8,9). The value of n can be several hundred thousand.
Restated in our own words, not a quote from Meesho or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I would ask: if one activity ends at the moment another starts, can both be chosen? Is the start always before the finish? Are the arrays unsorted? Can there be duplicates? Do I return the count or the chosen activities? What is the answer for no activities? How many activities can there be?
I would assume touching is allowed, start is before finish, the input is unsorted and may contain duplicates, a count is enough, and the empty list gives 0. With n up to a few hundred thousand I want O(n log n).
Brute force
Say the obvious answer and why it is too slow.
Try every subset of activities, check each for overlaps, and keep the largest valid subset. With n activities there are 2^n subsets and each check compares pairs, so it is exponential and stops being usable around 20 to 25 activities. A middle option is a DP over activities sorted by finish, where each activity looks back at all earlier ones for the best compatible chain. That is O(n²): fine for small n, but wasteful at 100,000 and more work than the problem needs.
The real issue is that these methods keep asking which combination is best, when one simple local rule can already settle each choice.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(n × 2^n)
- Time
- O(n log n)
- Space
- O(n)
The pattern is a greedy choice by earliest finish time. Sort the activities by finish time. Keep the end of the last activity you picked. Walk through the sorted list and pick an activity whenever it starts at or after that end. Count the picks.
Why it is correct, by an exchange argument. Let G be the activity with the earliest finish. Take any best schedule S. If S does not contain G, look at its first activity F. F finishes no earlier than G, so every other activity in S, which starts after F ends, also starts after G ends. Swap F for G: the schedule is still valid and still has the same size. So some best schedule begins with G. After choosing G, the rest of the problem is the same question on the activities that start at or after G ends, and the same argument applies again. Repeating it shows the greedy picks are never worse than any other schedule.
Other rules fail. Earliest start can choose one very long activity that blocks all the others. Shortest duration can choose a tiny activity in the middle that blocks two others that would have fit around it. Only finishing early guarantees the most room for what follows. The sort is O(n log n) and the scan is O(n). I would say it aloud as: always take the activity that frees the room soonest.
Walk it through
A dry run on the example, step by step.
| Activity (start,end) | Last end kept | Starts at or after it? | Decision | Count |
|---|---|---|---|---|
| (1,2) | none | yes | take | 1 |
| (3,4) | 2 | yes (3 >= 2) | take | 2 |
| (0,6) | 4 | no (0 < 4) | skip | 2 |
| (5,7) | 4 | yes (5 >= 4) | take | 3 |
| (8,9) | 7 | yes (8 >= 7) | take | 4 |
| (5,10) | 9 | no (5 < 9) | skip | 4 |
Use starts [1,3,0,5,8,5] and finishes [2,4,6,7,9,10]. Sorted by finish, the list is (1,2), (3,4), (0,6), (5,7), (8,9), (5,10). The room starts free. (1,2) starts after nothing, so take it; the last end is now 2. (3,4) starts at 3, at least 2, so take it; last end 4. (0,6) starts at 0, before 4, so skip it. (5,7) starts at 5, at least 4, take it; last end 7. (8,9) starts at 8, at least 7, take it; last end 9. (5,10) starts at 5, before 9, so skip it.
Four activities are taken, so the answer is 4. The trace table shows the last end, the test and the count at each step. The long activity (0,6) was skipped even though it looked attractive: it would have blocked both (3,4) and (5,7).
The code
Runnable JavaScript, checked against test cases.
function maxActivities(start, finish) {
const activities = start
.map((begin, i) => ({ begin, end: finish[i] }))
.sort((a, b) => a.end - b.end);
let lastEnd = -Infinity;
let chosen = 0;
for (const activity of activities) {
if (activity.begin >= lastEnd) {
chosen++;
lastEnd = activity.end;
}
}
return chosen;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
Empty input: the loop does not run and the count is 0. One activity: it is taken, count 1. All activities overlapping: only the one with the earliest finish is taken. Activities that touch end to start are all accepted, because the test is start greater than or equal to the last end.
Duplicates: the second copy starts before the end of the first, so it is skipped. Activities with the same finish time: whichever comes first is taken and the others start before that finish, so they are skipped; the order among them does not change the count. The first comparison uses negative Infinity as the last end, so the first pick needs no special case. The caller's arrays are never changed, because the pairs are copied into new objects before the sort.
Follow-ups to expect
Where the interviewer pushes next.
- How would you return the chosen activities themselves, not just the count?
- What changes if each activity has a profit, and why is greedy no longer enough?
- How would you find the minimum number of rooms needed to hold all the activities?
- How would you show that picking the shortest activity first can be wrong?
- How would the code change if activities that touch were not allowed?
Where candidates slip
The mistakes this problem punishes.
The main slip is a wrong greedy rule: sorting by start time, by length, or by the number of conflicts. Each has a small counterexample, and an interviewer will ask for one. The next is sorting only the finish array and leaving the starts in place, so the pairs break. Zip them first.
Others: using strict greater than when comparing a start with the last end, which loses touching activities when the problem allows them; sorting with the default comparator, which orders numbers as text and puts 10 before 2; updating the last end when an activity is skipped; and forgetting that the answer is a count, not the list. If the problem forbids touching, the comparison must become strictly greater, so read the statement carefully.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.