Day 36 of 100 days dsa coding challenge

Taking on a new challenge: solving GeeksforGeeks POTD daily and sharing my solutions! 💻🔥
The goal: sharpen problem-solving skills, level up coding, and learn something new every day. Follow my journey! 🚀

100DaysOfCode #CodingChallenge #ProblemSolving #GeeksforGeeks #DeveloperJourney

Problem:

https://www.geeksforgeeks.org/problems/weighted-job-scheduling/1

Weighted Job Scheduling

Difficulty: Medium Accuracy: 71.83%

Given a 2D array jobs[][] of size n × 3, where each row represents a single job with the following details:
• jobs[i][0] : Start time of the job
• jobs[i][1] : End time of the job
• jobs[i][2] : Profit earned by completing the job
Find the maximum profit you can earn by scheduling non-overlapping jobs.
Note: Two jobs are said to be non-overlapping if the end time of one job is less than or equal to the start time of the next job. If a job ends at time X, another job can start exactly at time X.

Examples:
Input: jobs[][] = [[1, 2, 50],
[3, 5, 20],
[6, 19, 100],
[2, 100, 200]]
Output: 250
Explanation: The first and fourth jobs with the time range [1, 2] and [2, 100] can be chosen to give maximum profit of 50 + 200 = 250.
Input: jobs[][] = [[1, 3, 60],
[2, 5, 50],
[4, 6, 70],
[5, 7, 30]]
Output: 130
Explanation: The first and third jobs with the time range [1, 3] and [4, 6] can be chosen to give maximum profit of 60 + 70 = 130.
Constraints:
1 ≤ jobs.size() ≤ 105
1 ≤ jobs[i][0] < jobs[i][1] ≤ 109
1 ≤ jobs[i][2] ≤ 104

Solution:
import bisect

class Solution:
def maxProfit(self, jobs):
jobs.sort(key=lambda x: x[1])
n = len(jobs)
dp = [0] * (n + 1)
end_times = [job[1] for job in jobs]

    for i in range(1, n + 1):
        start, end, profit = jobs[i - 1]
        idx = bisect.bisect_right(end_times, start, 0, i - 1)
        dp[i] = max(dp[i - 1], dp[idx] + profit)

    return dp[n]