Maximum Profit in job scheduling

from typing import List
import bisect

class Solution:
    def jobScheduling(self, startTime: List[int], endTime: List[int], profit: List[int]) -> int:

        # Step 1: Combine start, end, profit into a single jobs list
        jobs = []
        for s, e, p in zip(startTime, endTime, profit):
            jobs.append((s, e, p))

        # Step 2: Sort jobs by end time (important for DP ordering)
        jobs.sort(key=lambda x: x[1])

        # Step 3: Extract the list of end times (for binary search later)
        ends = [e for _, e, _ in jobs]

        # Helper function: find index of last job that does NOT overlap
        # For a given job starting at "start", we want the rightmost job whose end <= start
        def get_non_overlapping_job(start, ends):
            return bisect.bisect_right(ends, start) - 1

        # Step 4: DP array where dp[i] = max profit we can earn by considering first i jobs
        dp = [0] * (len(jobs) + 1)

        # Step 5: Process jobs in order of end time
        for i in range(1, len(jobs) + 1):
            start, end, profit = jobs[i-1]

            # Find last non-overlapping job index
            j = get_non_overlapping_job(start, ends)

            # Option 1: skip current job → dp[i-1]
            # Option 2: take current job → profit + dp[j+1]
            dp[i] = max(dp[i-1], profit + dp[j+1])

        # Step 6: Final answer is max profit after considering all jobs
        return dp[len(jobs)]