Introduction

In this blog post, we will explore how to solve the LeetCode problem "1235" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like Chatmagic, we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

Problem Statement

We have n jobs, where every job is scheduled to be done from startTime[i] to endTime[i], obtaining a profit of profit[i]. You're given the startTime, endTime and profit arrays, return the maximum profit you can take such that there are no two jobs in the subset with overlapping time range. If you choose a job that ends at time X you will be able to start another job that starts at time X. Example 1: Input: startTime = [1,2,3,3], endTime = [3,4,5,6], profit = [50,10,40,70] Output: 120 Explanation: The subset chosen is the first and fourth job. Time range [1-3]+[3-6] , we get profit of 120 = 50 + 70. Example 2: Input: startTime = [1,2,3,4,6], endTime = [3,5,10,6,9], profit = [20,20,100,70,60] Output: 150 Explanation: The subset chosen is the first, fourth and fifth job. Profit obtained 150 = 20 + 70 + 60. Example 3: Input: startTime = [1,1,1], endTime = [2,3,4], profit = [5,6,4] Output: 6 Constraints: 1 <= startTime.length == endTime.length == profit.length <= 5 * 104 1 <= startTime[i] < endTime[i] <= 109 1 <= profit[i] <= 104

Explanation

Here's the breakdown of the solution:

• Sort Jobs: Sort the jobs based on their end times. This allows us to process jobs in a way that makes it easier to find non-overlapping jobs that finish earlier.
• Dynamic Programming: Use dynamic programming to build a solution. dp[i] will store the maximum profit achievable considering jobs up to index i in the sorted order. The key decision is whether to include the current job i or not.

• Binary Search: If we include job i, we need to find the latest non-overlapping job that finishes before the start time of job i. Binary search is used efficiently find such a job in O(log n) time.

• Runtime Complexity: O(n log n) due to sorting and binary search. Storage Complexity: O(n) for the dp array.

Code

    def jobScheduling(startTime, endTime, profit):
    """
    Calculates the maximum profit achievable from scheduling non-overlapping jobs.

    Args:
        startTime: A list of job start times.
        endTime: A list of job end times.
        profit: A list of job profits.

    Returns:
        The maximum profit.
    """

    jobs = sorted(zip(startTime, endTime, profit), key=lambda x: x[1])  # Sort by end time
    n = len(jobs)
    dp = [0] * n

    dp[0] = jobs[0][2]  # Initialize with the profit of the first job

    def binary_search(end_time):
        """
        Finds the latest job that ends before the given end_time.

        Args:
            end_time: The end time to search for.

        Returns:
            The index of the latest non-overlapping job, or -1 if none exists.
        """
        low = 0
        high = n - 1
        result = -1
        while low <= high:
            mid = (low + high) // 2
            if jobs[mid][1] <= end_time:
                result = mid
                low = mid + 1
            else:
                high = mid - 1
        return result

    for i in range(1, n):
        current_profit = jobs[i][2]
        prev_job_index = binary_search(jobs[i][0])  # Find non-overlapping job

        if prev_job_index != -1:
            current_profit += dp[prev_job_index]

        dp[i] = max(dp[i - 1], current_profit)  # Choose max profit: with or without current job

    return dp[n - 1]