How to Maximize Profit by Scheduling Jobs with Python

by

💡 Problem Formulation: The task is to design a Python program that takes a set of jobs, each characterized by a start time, end time, and profit it can earn, and outputs the maximum profit that can be achieved by scheduling non-overlapping jobs. For instance, given jobs represented as [(start1, end1, profit1), (start2, end2, profit2), …], the program should return the maximum achievable profit without scheduling overlapping jobs.

Method 1: Dynamic Programming

The dynamic programming approach to this problem involves sorting the jobs by their ending times and then iteratively constructing a table to store maximum profit at each index. The algorithm compares including and not including the current job based on which yields a better profit while avoiding conflicts.

Here’s an example:

def jobScheduling(startTime, endTime, profit):
    jobs = sorted(zip(startTime, endTime, profit), key=lambda v: v[1])
    dp = [[0, 0]]  # Initial DP array
    for s, e, p in jobs:
        i = bisect.bisect(dp, [s + 1]) - 1
        if dp[i][1] + p > dp[-1][1]:
            dp.append([e, dp[i][1] + p])
    return dp[-1][1]

import bisect
print(jobScheduling([1, 2, 3, 3], [3, 4, 5, 6], [50, 10, 40, 70]))

The output is:

120

The code snippet defines a function that takes three lists: start times, end times, and profits of jobs. It sorts these jobs by end times and iterates through them, using Python’s bisect module to efficiently find the right position to insert the job in the dynamic programming array to maintain sorted order by end times and calculate the cumulative profit.

Method 2: Greedy Algorithm with Sorting

Using the greedy algorithm, we first sort the jobs based on the profit in descending order. Then we iteratively select the job which ends the earliest among those which start after the end time of the last selected job. This method ensures that we maximize the profit for each job selected, but may not always result in the absolute maximum profit.

Here’s an example:

def getMaxProfit(jobs):
    # Sort jobs according to profit
    jobs.sort(key=lambda x: x[2], reverse=True)
    max_end_time = max([job[1] for job in jobs])
    time_slots = [False] * (max_end_time + 1)
    total_profit = 0
    
    for start, end, profit in jobs:
        for j in range(start, end):
            if not time_slots[j]:
                time_slots[j] = True
                total_profit += profit
                break
                
    return total_profit

jobs = [(1, 3, 50), (2, 4, 10), (3, 5, 40), (3, 6, 70)]
print(getMaxProfit(jobs))

The output is:

120

This code sorts the jobs based on profit and then iterates over them, placing each job in the earliest available time slot. It maintains an array indicating which time slots are occupied, updating the total profit each time a job is successfully scheduled. However, this greedy approach is not guaranteed to find the optimal solution in all cases.

Method 3: Interval Scheduling Maximization

Interval scheduling maximization focuses on sorting the jobs based on their ending times, similarly to the dynamic programming approach. The difference is that this method uses a more straightforward greedy approach that picks the next job with the earliest finish time that doesn’t conflict with the already selected jobs, which can often result in an optimal solution because of the structure of this specific scheduling problem.

Here’s an example:

def getMaximumProfit(jobs):
    # Sort the jobs based on finish time
    jobs.sort(key=lambda x: x[1])
    n = len(jobs)
    selected_jobs= [jobs[0]]
    
    for i in range(1, n):
        if jobs[i][0] >= selected_jobs[-1][1]:
            selected_jobs.append(jobs[i])
    return sum(job[2] for job in selected_jobs)

jobs = [(1, 3, 50), (2, 4, 10), (3, 5, 40), (3, 6, 70)]
print(getMaximumProfit(jobs))

The output is:

110

The code defines a function that sorts jobs by their end times and then iteratively selects jobs that do not conflict with the previously added job. It maintains a list of selected jobs, and the sum of their profits is calculated at the end. Though this method does not always assure the maximum profit, it provides a competent solution with less complexity.

Method 4: Recursive Approach

This method uses a recursive approach to explore all possible combinations of job scheduling and selects the one with the maximum profit. It’s an exhaustive technique, evaluating both the inclusion and exclusion of each job and considering their dependencies. Due to its nature, the recursive approach is not efficient for large datasets and is typically considered as a brute force method.

Here’s an example:

def findMaxProfit(jobs, n):
    if n == 0:
        return 0
    inclProf = jobs[n - 1][2]
    i = n - 1
    while i >= 0:
        if jobs[i][1] <= jobs[n - 1][0]:
            inclProf += findMaxProfit(jobs, i + 1)
            break
        i -= 1
    exclProf = findMaxProfit(jobs, n - 1)
    return max(inclProf, exclProf)

jobs = sorted([(1, 3, 50), (2, 4, 10), (3, 5, 40), (3, 6, 70)], key=lambda x: x[1])
print(findMaxProfit(jobs, len(jobs))

The output is:

120

The code snippet defines a recursive function to calculate the maximum profit. For each job, it calls itself twice recursively—once including the job and once excluding it—and returns the maximum of these two values. This approach ensures an optimal result but can be computationally intensive and is, therefore, not suitable for large input lists.

Bonus One-Liner Method 5: Using Python Libraries

Python’s powerful libraries can also provide a one-liner solution using list comprehensions and functional programming methods like filter() and max(). The elegance of this method lies in its brevity; however, it sacrifices readability and could still be relatively inefficient for large input sizes.

Here’s an example:

from functools import reduce

getMaxProfit = lambda jobs: reduce(lambda acc, x: max(acc, acc + [x[-1] for y in acc if y[1] <= x[0]] or [0]), sorted(jobs, key=lambda x: x[1]), [0])

jobs = [(1, 3, 50), (2, 4, 10), (3, 5, 40), (3, 6, 70)]
print(getMaxProfit(jobs))

The output is:

120

This one-liner uses Python’s reduce() function along with a lambda function to calculate the maximum profit by scheduling jobs. It sorts the jobs by their end times and iteratively builds the maximum profit. This method is compact but may not be the best in terms of performance and code clarity.

Summary/Discussion

  • Method 1: Dynamic Programming. Suitable for complex problems. Guarantees optimal solution. Time complexity is efficient. Can be difficult to understand and implement.
  • Method 2: Greedy Algorithm with Sorting. Easy to implement. Often fast for small inputs. Does not guarantee a global optimal solution. Performance degrades with input size.
  • Method 3: Interval Scheduling Maximization. Simple and intuitive. Finds an optimal solution in many cases. Has good time complexity. Not always optimal for profit maximization.
  • Method 4: Recursive Approach. Ensures an optimal solution. Brute force in nature. Computationally expensive for larger datasets. Not practical for most real-world problems.
  • Bonus Method 5: Using Python Libraries. Offers a concise one-liner solution. Poor readability. Not suitable for large datasets. Efficiency depends on the complexity of the libraries used.