Activity Selection Profit LeetCode (Activity Selection Problem)

Given N jobs where every job is represented by following three elements of it.

• Start Time
• Finish Time
• Profit or Value Associated

Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Example:

1. Input: Number of Jobs n = 4
2. Job Details {Start Time, Finish Time, Profit}
1. Job 1:  {1, 2, 50} 
2. Job 2:  {3, 5, 20}
3. Job 3:  {6, 19, 100}
4. Job 4:  {2, 100, 200}
3. Output: The maximum profit is 250.
4. We can get the maximum profit by scheduling jobs 1 and 4.

Note that there is longer schedules possible Jobs 1, 2 and 3 but the profit with this schedule is 20+50+100 which is less than 250. 

This is an interesting interview problem that is well discussed in GeeksForGeeks- Activity Selection Problem A collection of hundreds of interview questions and solutions are available in our blog at Interview Question

Solution:

-we use a recursive approach to solve this problem in O(n^2) when used DP

Solution