← Back to DSA Course | Chapter 15: Greedy Algorithms | Lesson 2 of 5

Activity Selection समस्या

Activity selection अपने दिन को इस तरह plan करने जैसा है कि बिना किसी overlap के सबसे ज़्यादा events fit हो जाएं, हमेशा वह चुनते हुए जो सबसे जल्दी खत्म हो।

In this page:

  1. Problem Idea
  2. Sort by Finish Time
  3. Greedy Selection
  4. Why It Works
  5. Practice
Syntax
markup 
activities.sort(key=lambda a: a[1])    # (start, finish)
selected = [activities[0]]
last_finish = activities[0][1]
for start, finish in activities[1:]:
    if start >= last_finish:
        selected.append((start, finish))
        last_finish = finish

Problem Idea

Activities की एक list दी गई जिनमें हर एक एक start और end time occupy करती है, activity selection problem पूछता है कि एक person बिना किसी overlap के ज़्यादा से ज़्यादा कितनी activities attend कर सकता है।

उदाहरण: Problem Idea

#include <iostream>
using namespace std;
int main() {
	int start[] = {1,3,0,5,8,5}, finish[] = {2,4,6,7,9,9};
	cout << "Max activities one person can attend, no two overlapping, from " << 6 << " candidates";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		int[] start = {1,3,0,5,8,5}, finish = {2,4,6,7,9,9};
		System.out.println("Max activities one person can attend, no two overlapping, from 6 candidates");
	}
}
start, finish = [1,3,0,5,8,5], [2,4,6,7,9,9]
print("Max activities one person can attend, no two overlapping, from 6 candidates")
#include <stdio.h>
int main() {
	int start[] = {1,3,0,5,8,5}, finish[] = {2,4,6,7,9,9};
	printf("Max activities one person can attend, no two overlapping, from 6 candidates");
	return 0;
}

Sort by Finish Time

इस problem के लिए proven greedy rule है हमेशा activities को उनके finish time के order में consider करना, सबसे पहले वाले से शुरू — start time से नहीं, duration से नहीं, specifically इससे कि हर activity कब खत्म होती है।

उदाहरण: Sort by Finish Time

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	vector<pair<int,int>> act = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
	sort(act.begin(), act.end(), [](auto&a, auto&b){ return a.second < b.second; });
	cout << "Earliest-finishing activity: (" << act[0].first << "," << act[0].second << ")";
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[][] act = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
		Arrays.sort(act, (a,b) -> a[1]-b[1]);
		System.out.println("Earliest-finishing activity: (" + act[0][0] + "," + act[0][1] + ")");
	}
}
act = [(1,2),(3,4),(0,6),(5,7),(8,9),(5,9)]
act.sort(key=lambda a: a[1])
print(f"Earliest-finishing activity: ({act[0][0]},{act[0][1]})")
#include <stdio.h>
int main() {
	int act[6][2] = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
	for (int i = 0; i < 6; i++)
		for (int j = i+1; j < 6; j++)
			if (act[j][1] < act[i][1]) { int t0=act[i][0],t1=act[i][1]; act[i][0]=act[j][0]; act[i][1]=act[j][1]; act[j][0]=t0; act[j][1]=t1; }
	printf("Earliest-finishing activity: (%d,%d)", act[0][0], act[0][1]);
	return 0;
}

Greedy Selection

एक activity चुनने के बाद, अगली selected वह होनी चाहिए जो उनमें से earliest-finishing हो जो पिछली वाली खत्म होने के बाद शुरू होती हैं, जो selection को non-overlapping और maximal दोनों रखता है।

उदाहरण: Greedy Selection

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
	vector<pair<int,int>> act = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
	sort(act.begin(), act.end(), [](auto&a, auto&b){ return a.second < b.second; });
	int count = 1, lastFinish = act[0].second;
	for (int i = 1; i < 6; i++)
		if (act[i].first >= lastFinish) { count++; lastFinish = act[i].second; }
	cout << "Max non-overlapping activities: " << count;
	return 0;
}
import java.util.*;
public class Main {
	public static void main(String[] args) {
		int[][] act = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
		Arrays.sort(act, (a,b) -> a[1]-b[1]);
		int count = 1, lastFinish = act[0][1];
		for (int i = 1; i < 6; i++)
			if (act[i][0] >= lastFinish) { count++; lastFinish = act[i][1]; }
		System.out.println("Max non-overlapping activities: " + count);
	}
}
act = [(1,2),(3,4),(0,6),(5,7),(8,9),(5,9)]
act.sort(key=lambda a: a[1])
count, last_finish = 1, act[0][1]
for s, f in act[1:]:
    if s >= last_finish:
        count += 1
        last_finish = f
print("Max non-overlapping activities:", count)
#include <stdio.h>
int main() {
	int act[6][2] = {{1,2},{3,4},{0,6},{5,7},{8,9},{5,9}};
	for (int i = 0; i < 6; i++)
		for (int j = i+1; j < 6; j++)
			if (act[j][1] < act[i][1]) { int t0=act[i][0],t1=act[i][1]; act[i][0]=act[j][0]; act[i][1]=act[j][1]; act[j][0]=t0; act[j][1]=t1; }
	int count = 1, lastFinish = act[0][1];
	for (int i = 1; i < 6; i++)
		if (act[i][0] >= lastFinish) { count++; lastFinish = act[i][1]; }
	printf("Max non-overlapping activities: %d", count);
	return 0;
}

Why It Works

Earliest-finishing activity चुनना provably safe है क्योंकि यह इसके बाद आने वाली किसी भी activities के लिए सबसे बड़ी possible बची time window छोड़ता है — कोई भी और choice भविष्य के लिए सिर्फ बराबर या कम room छोड़ सकता है।

उदाहरण: Why It Works

#include <iostream>
using namespace std;
int main() {
	cout << "Earliest finish leaves the largest remaining window -- any other choice could only leave less room";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Earliest finish leaves the largest remaining window -- any other choice could only leave less room");
	}
}
print("Earliest finish leaves the largest remaining window -- any other choice could only leave less room")
#include <stdio.h>
int main() {
	printf("Earliest finish leaves the largest remaining window -- any other choice could only leave less room");
	return 0;
}

Practice

Paper पर overlapping time ranges वाली कुछ activities lay out करने की कोशिश करें, उन्हें finish time से sort करें, और बारी-बारी हर compatible एक चुनने के through चलें — जो count आप पाते हैं वह greedy-optimal answer है।

उदाहरण: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "Lay out overlapping activities on paper, sort by finish time, pick each compatible one in turn";
	return 0;
}
public class Main {
	public static void main(String[] args) {
		System.out.println("Lay out overlapping activities on paper, sort by finish time, pick each compatible one in turn");
	}
}
print("Lay out overlapping activities on paper, sort by finish time, pick each compatible one in turn")
#include <stdio.h>
int main() {
	printf("Lay out overlapping activities on paper, sort by finish time, pick each compatible one in turn");
	return 0;
}
Related Topics

Selection Sort क्या है · Coin Change समस्या · N-Queens समस्या · Two Sum समस्या

{# common_mistakes/chapter_summary/browser_support: on Hindi pages the view already swaps in the hi_ translation fields (or blanks these out if untranslated), so this renders correctly for both languages without a lang_code check here. #}
आम गलतियां
  1. Finish time के बजाय start time से sort करना, जो एक लंबी activity चुन सकता है जो कई दूसरों को block करे।
  2. start >= lastFinish बनाम start > lastFinish inconsistently उपयोग करना जब boundary पर touch करने वाली activities allowed हों।
  3. Sort करने के बाद हमेशा पहली activity चुनना भूल जाना।
🔒

Chapter Quiz — Complete all 5 topics to unlock

0/5 topics done

Complete these topics first:

← Previous Lesson Greedy Introduction Next Lesson → Fractional Knapsack

Login to run this code

C/C++/Java/PHP execution requires a free account. Your code is saved — you'll land right back in the editor after logging in.