इस article में आप Job Sequencing Problem को बिल्कुल zero level से advanced level तक बहुत ही आसान Hindi में समझने वाले हैं। यहाँ आप जानेंगे कि Job Sequencing Problem क्या होता है, इसे Greedy Algorithm से कैसे solve करते हैं, step-by-step example, code implementation, time complexity, real life examples और interview में पूछे जाने वाले सवाल।
अगर आप Data Structures & Algorithms सीख रहे हैं या coding interview की तैयारी कर रहे हैं, तो यह article आपके लिए complete guide साबित होगा।
Job Sequencing Problem क्या है?
Job Sequencing Problem एक famous scheduling problem है जिसमें हमारे पास कई jobs होती हैं और हर job के साथ दो चीजें जुड़ी होती हैं:
- Deadline – job को किस समय से पहले complete करना है
- Profit – job करने पर कितना profit मिलेगा
हमारा goal होता है:
दिए गए jobs को इस तरह schedule करना कि कुल profit maximum हो और एक time slot में सिर्फ एक job ही हो।
Job Sequencing Problem – Formal Problem Statement
मान लीजिए हमारे पास N jobs हैं। हर job को 1 unit time लगता है और हर job के पास:
| Job | Deadline | Profit |
| J1 | 2 | 100 |
| J2 | 1 | 19 |
| J3 | 2 | 27 |
| J4 | 1 | 25 |
| J5 | 3 | 15 |
हमें jobs इस तरह से schedule करनी हैं कि deadline के अंदर job complete हो और total profit maximum बने।
Greedy Algorithm Approach Explained
अब तक आपने यह समझ लिया कि Job Sequencing Problem में हमारा goal होता है –Maximum profit कमाना और हर job को उसके deadline से पहले पूरा करना।
Job Sequencing Problem को solve करने के लिए हम Greedy Algorithm का use करते हैं, क्योंकि इस problem में हर step पर locally best decision लेने से global optimum result मिलता है। यहाँ greedy choice यह होती है कि हम हमेशा सबसे पहले वही job चुनते हैं जिसका profit सबसे अधिक हो।
सबसे पहले सभी jobs को उनके profit के अनुसार descending order में sort कर दिया जाता है। इसके बाद maximum deadline निकालकर उतने ही time slots बनाए जाते हैं।
फिर sorted jobs को एक-एक करके लिया जाता है और हर job को उसके deadline से पहले वाले सबसे आख़िरी available (latest free) slot में place किया जाता है।
अगर उस slot पर पहले से कोई job मौजूद हो तो उससे पहले वाले slot को check किया जाता है। इस तरह हम high profit वाली jobs को priority देते हुए schedule करते हैं और total profit को maximum बना लेते हैं।
यह भी पढ़ें : ग्रीडी एल्गोरिदम क्या है | What is Greedy Algorithm in Hindi
Job Sequencing Problem: Step-by-Step Solution
Step 1: Jobs को Profit के अनुसार Descending order में sort करें
Profit जितना ज्यादा, priority उतनी ज्यादा।
Step 2: Maximum deadline निकालें
इससे हमें पता चलेगा कि total कितने slots चाहिए।
Step 3: Slot array बनाएं
यह बताने के लिए कि कौन सा slot खाली है।
Step 4: हर job को उसके possible latest slot में डालें
अगर उस slot पर पहले से कोई job है, तो उससे पहले वाले slot को check करें।
Example 1 – Simple Example
Jobs:
| Job | Deadline | Profit |
| A | 2 | 100 |
| B | 1 | 19 |
| C | 2 | 27 |
| D | 1 | 25 |
| E | 3 | 15 |
Step 1: Profit descending order
A(100), C(27), D(25), B(19), E(15)
Step 2: Slots = 3
Slots = [ –, –, – ]
Step 3: Scheduling
- A → slot 2
- C → slot 1
- D → slot 1 occupied → reject
- B → slot 1 occupied → reject
- E → slot 3
Final Slots: [C, A, E]
Total Profit = 27 + 100 + 15 = 142
Example 2 – Larger Example
| Job | Deadline | Profit |
| J1 | 4 | 20 |
| J2 | 1 | 10 |
| J3 | 1 | 40 |
| J4 | 1 | 30 |
Sorted: J3(40), J4(30), J1(20), J2(10)
Slots = 4
Final Schedule:
Slot1 → J3
Slot4 → J1
Total Profit = 60
Time & Space Complexity Analysis
| Operation | Complexity |
| Sorting jobs | O(n log n) |
| Slot allocation | O(n × maxDeadline) |
| Total Time | O(n log n) |
| Space Complexity | O(maxDeadline) |
C++ Implementation – Job Sequencing Problem
#include <bits/stdc++.h>
using namespace std;
struct Job {
char id;
int deadline, profit;
};
bool compare(Job a, Job b) {
return a.profit > b.profit;
}
void jobSequencing(Job jobs[], int n) {
sort(jobs, jobs+n, compare);
int maxDeadline = 0;
for(int i=0;i<n;i++)
maxDeadline = max(maxDeadline, jobs[i].deadline);
vector<int> slot(maxDeadline+1, -1);
for(int i=0;i<n;i++) {
for(int j=jobs[i].deadline; j>0; j--) {
if(slot[j] == -1) {
slot[j] = i;
break;
}
}
}
cout<<"Selected Jobs: ";
for(int i=1;i<=maxDeadline;i++) {
if(slot[i] != -1)
cout<<jobs[slot[i]].id<<" ";
}
}
int main() {
Job jobs[] = {{'A',2,100},{'B',1,19},{'C',2,27},{'D',1,25},{'E',3,15}};
int n = sizeof(jobs)/sizeof(jobs[0]);
jobSequencing(jobs, n);
}
यह भी पढ़ें : Knapsack Problem in Algorithm क्या है – One Article to Clear All Your Concepts in Hindi
निष्कर्ष (Conclusion)
अब आपने समझ लिया कि Job Sequencing Problem क्या है, इसे Greedy Algorithm से कैसे solve किया जाता है, real life examples और code implementation के साथ। अगर आप DSA सीख रहे हैं या interview की तैयारी कर रहे हैं तो यह problem आपके लिए बहुत महत्वपूर्ण है।
इस article को बार-बार पढ़िए, खुद examples solve कीजिए और coding practice करते रहिए – यही success का shortcut है
FAQs
Q1. क्या हर job select होगी?
Ans. नहीं, केवल profitable jobs जिनके लिए slot available हो।
Q2. अगर deadlines same हों तो?
Ans. Profit के आधार पर decide किया जाएगा।
Q3. Job Sequencing Problem में Greedy Algorithm क्यों use करते हैं?
Ans. क्योंकि इसमें हर step पर सबसे ज्यादा profit देने वाली job चुनने से overall maximum profit मिलता है।
Q4. क्या हर job को schedule किया जा सकता है?
Ans. नहीं, केवल वही jobs schedule होती हैं जिनके लिए deadline से पहले free time slot available होता है।
Q5. Job Sequencing Problem का real life use कहाँ होता है?
Ans. Freelancing projects, task scheduling, exam planning और resource management जैसे कई real life scenarios में।
यह भी पढ़ें : PM-KUSUM Yojana 2025 – Solar Pump Subsidy, Benefits, Online Apply & Latest Update
