Weighted Job Scheduling Problem Statement

You have 'N' jobs, each with a start time, end time, and profit. Your task is to identify the maximum profit that can be earned by scheduling these jobs such that no two jobs overlap.

Input:

The first line contains an integer 'T' denoting the number of test cases. For each test case: - The first line contains an integer 'N' denoting the number of jobs. - The second line contains 'N' space-separated integers representing the start times of the jobs. - The third line contains 'N' space-separated integers representing the end times of the jobs. - The fourth line contains 'N' space-separated integers representing the profits of the jobs.

Output:

For each test case, output the maximum profit obtainable. Each result should be printed on a new line.

Example:

Input:

1 4 1 2 3 3 3 5 4 5 50 10 40 70

Output:

120

Constraints:

1

Question

Weighted Job Scheduling Problem Statement

You have 'N' jobs, each with a start time, end time, and profit. Your task is to identify the maximum profit that can be earned by scheduling these jobs such that no two jobs overlap.

Input:

The first line contains an integer 'T' denoting the number of test cases. 
For each test case: 
- The first line contains an integer 'N' denoting the number of jobs. 
- The second line contains 'N' space-separated integers representing the start times of the jobs. 
- The third line contains 'N' space-separated integers representing the end times of the jobs. 
- The fourth line contains 'N' space-separated integers representing the profits of the jobs.

Output:

For each test case, output the maximum profit obtainable. Each result should be printed on a new line.

Example:

Input:

1 
4 
1 2 3 3 
3 5 4 5 
50 10 40 70

Output:

Constraints:

1 <= T <= 100
1 <= N <= 3000
1 <= Start[i] < End[i] <= 10^9
1 <= Profit[i] <= 10^9

Note:

The start time of one job can be equal to the end time of another.

Follow-up:

Can you devise an algorithm that solves this problem in O(N*log(N)) time complexity?

Accepted Answer

The Weighted Job Scheduling problem involves maximizing profit by scheduling non-overlapping jobs with start time, end time, and profit given.

Sort the jobs based on their end times in ascending order.
Initialize an array 'dp' to store the maximum profit that can be earned by scheduling jobs up to that index.
For each job, find the maximum profit by either including or excluding the current job based on non-overlapping condition.
Return the maximum profit from the 'dp' array.
Example: For input [1, 2, 3] as start times, [3, 5, 4] as end times, and [50, 10, 40] as profits, the maximum profit would be 120.

Weighted Job Scheduling Problem Statement

Input:

Output:

Example:

Input:

Output:

Constraints:

Note:

Follow-up:

PhonePe Software Developer interview questions & answers

Popular interview questions of Software Developer