How to prefer longer intervals in weighted interval scheduling

Question

Weighted interval scheduling has a fast solution that is reasonably easy to implement. Here is some code in python:

# A class to store a Job
class Job:
    def __init__(self, start, finish, profit):
        self.start = start
        self.finish = finish
        self.profit = profit
 
 
# Function to perform a binary search on the given jobs, which are sorted
# by finish time. The function returns the index of the last job, which
# doesn't conflict with the given job, i.e., whose finish time is
# less than or equal to the given job's start time.
def findLastNonConflictingJob(jobs, n):
 
    # search space
    (low, high) = (0, n)
 
    # iterate till the search space is exhausted
    while low <= high:
        mid = (low + high) // 2
        if jobs[mid].finish <= jobs[n].start:
            if jobs[mid + 1].finish <= jobs[n].start:
                low = mid + 1
            else:
                return mid
        else:
            high = mid - 1
 
    # return the negative index if no non-conflicting job is found
    return -1
 
 
# Function to print the non-overlapping jobs involved in maximum profit
# using dynamic programming
def findMaxProfitJobs(jobs):
 
    # sort jobs in increasing order of their finish times
    jobs.sort(key=lambda x: x.finish)
    print([(jobs[i].start, jobs[i].finish) for i in range(len(jobs))])
 
    # get the number of jobs
    n = len(jobs)
 
    # `maxProfit[i]` stores the maximum profit possible for the first `i` jobs, and
    # `tasks[i]` stores the index of jobs involved in the maximum profit
    maxProfit = [None] * n
    tasks = [[] for _ in range(n)]
 
    # initialize `maxProfit[0]` and `tasks[0]` with the first job
    maxProfit[0] = jobs[0].profit
    tasks[0].append(0)
 
    # fill `tasks[]` and `maxProfit[]` in a bottom-up manner
    for i in range(1, n):
 
        # find the index of the last non-conflicting job with the current job
        index = findLastNonConflictingJob(jobs, i)
 
        # include the current job with its non-conflicting jobs
        currentProfit = jobs[i].profit
        if index != -1:
            currentProfit += maxProfit[index]
 
        # if including the current job leads to the maximum profit so far
        if maxProfit[i - 1] <= currentProfit:
            maxProfit[i] = currentProfit
 
            if index != -1:
                tasks[i] = tasks[index]
            tasks[i].append(i)
 
        # excluding the current job leads to the maximum profit so far
        else:
            tasks[i] = tasks[i - 1][:]
            maxProfit[i] = maxProfit[i - 1]
 
    # `maxProfit[n-1]` stores the maximum profit
    print("The maximum profit is", maxProfit[n - 1])
 
    # `tasks[n-1]` stores the index of jobs involved in the maximum profit
    print("The jobs involved in the maximum profit are", end=' ')
    for i in tasks[n - 1]:
        print((jobs[i].start, jobs[i].finish, jobs[i].profit), end=' ')
 
 
if __name__ == '__main__':
    jobs = [
        Job(0, 3, 4), Job(0, 7, 8), Job(4, 7, 4)
    ]
 
    findMaxProfitJobs(jobs)

The code outputs:

The jobs involved in the maximum profit are (0, 3, 4) (4, 7, 4) 

In this case the two weights of the two intervals (0,3) and (4,7) sum to the same value as the weight of the interval (0, 7). When this happens I would like the algorithm to return the single longer interval but this code returns the two shorter ones.

How can the code/algorithm be modified to prefer longer intervals as a tie breaker?

Answer 1

Rather than longer intervals, the proper criteria would be the lower number of intervals. So we are solving using two criteria:

1. Provide maximum weight (profit)
2. Using the minimum number of jobs

Note: an issue with the current code is the use of shallow copy rather than deepcopy i.e.

 tasks[i] = tasks[i - 1][:]  # Shallow copy
 tasks[i] = deepcopy(tasks[i-1]  # Deep copy

Use of shallow copy while providing the correct profit provides incorrect jobs in more complex cases.

Code

from copy import deepcopy

# A class to store a Job
class Job:
    def __init__(self, start, finish, profit):
        self.start = start
        self.finish = finish
        self.profit = profit
 
 
# Function to perform a binary search on the given jobs, which are sorted
# by finish time. The function returns the index of the last job, which
# doesn't conflict with the given job, i.e., whose finish time is
# less than or equal to the given job's start time.
def findLastNonConflictingJob(jobs, n):
 
    # search space
    (low, high) = (0, n)
 
    # iterate till the search space is exhausted
    while low <= high:
        mid = (low + high) // 2
        if jobs[mid].finish <= jobs[n].start:
            if jobs[mid + 1].finish <= jobs[n].start:
                low = mid + 1
            else:
                return mid
        else:
            high = mid - 1
 
    # return the negative index if no non-conflicting job is found
    return -1
 
 
# Function to print the non-overlapping jobs involved in maximum profit
# using dynamic programming
def findMaxProfitJobs(jobs):
 
    # sort jobs in increasing order of their finish times
    jobs.sort(key=lambda x: x.finish)
    print([(jobs[i].start, jobs[i].finish) for i in range(len(jobs))])
 
    # get the number of jobs
    n = len(jobs)
 
    # `maxProfit[i]` is a tuple containing the maximum profit possible for the 
    # first `i` jobs and the negative of the number of jobs to achieve 
    # this profit. We use negative intervals since when looking for max, 
    # the number of intervals will be minimized as a tie-breaker on profit
    # `tasks[i]` stores the index of jobs involved in the maximum profit
    maxProfit = [None] * n
    tasks = [[] for _ in range(n)]
 
    # initialize `maxProfit[0]` and `tasks[0]` with the first job
    maxProfit[0] = (jobs[0].profit, -1)
    tasks[0].append(0)
 
    # fill `tasks[]` and `maxProfit[]` in a bottom-up manner
    for i in range(1, n):
 
        # find the index of the last non-conflicting job with the current job
        index = findLastNonConflictingJob(jobs, i)
 
        # include the current job with its non-conflicting jobs
        currentProfit = (jobs[i].profit, -1)   # (profit, negative of number of jobs)
        if index != -1:
            # current tuple of profit and negative of number of intervals
            currentProfit = (currentProfit[0] + maxProfit[index][0], 
                             currentProfit[1] + maxProfit[index][1])
            
 
        # if including the current job leads to the maximum profit so far
        if maxProfit[i - 1] <= currentProfit:
            # comparison of tuple based upon profit and number of jobs
            maxProfit[i] = currentProfit
 
            if index != -1:
                tasks[i] = deepcopy(tasks[index])
            tasks[i].append(i)
 
        # excluding the current job leads to the maximum profit so far
        else:
            tasks[i] = deepcopy(tasks[i - 1])
            maxProfit[i] = maxProfit[i - 1]
 
    # `maxProfit[n-1]` stores the maximum profit
    print("The maximum profit is", maxProfit[n - 1])
 
    # `tasks[n-1]` stores the index of jobs involved in the maximum profit
    print("The jobs involved in the maximum profit are", end=' ')
    
    for i in tasks[n - 1]:
        print((jobs[i].start, jobs[i].finish, jobs[i].profit), end=' ')
    print()
 
 
if __name__ == '__main__':
    # Test 1
    print('Test 1')
    jobs = [
        Job(0, 3, 4), Job(0, 7, 8), Job(4, 7, 4)
    ]
    
    findMaxProfitJobs(jobs)
    
    # Test 2
    print('\nTest 2')
    jobs = [
        Job(2, 2, 50), Job(3, 5, 20), Job(6, 19, 100), Job(2, 100, 200)
    ]
 
    findMaxProfitJobs(jobs)

Output

Test 1
[(0, 3), (0, 7), (4, 7)]
The maximum profit is (8, -1)
Tasks [[0], [1], [1]]
The jobs involved in the maximum profit are (0, 7, 8) 

Test 2
[(2, 2), (3, 5), (6, 19), (2, 100)]
The maximum profit is (250, -2)
Tasks [[0], [0, 1], [0, 1, 2], [0, 3]]
The jobs involved in the maximum profit are (2, 2, 50) (2, 100, 200)