Total number of non overlapping subsets

Question

I am trying to solve this question. The essence of the problem is this:

Given a list of school classes with start and end times, find the total number of non-overlapping subsets.

I've written up a DP solution that I think is optimal in terms of time complexity - \$n * \log(n)\$.

'''
https://www.spoj.com/problems/ACTIV/
'''

from collections import defaultdict


def bin_search(classes, target):
    hi = len(classes)-1
    lo = 0
    while lo <= hi:
        mid = (hi + lo)//2
        if classes[mid][1] > target:
            hi = mid-1
        else:
            lo = mid+1
    return hi


def num_nonoverlapping(classes):
    classes.sort(key=lambda x: x[1])
    dp = [0] * len(classes)
    prefix_sum = defaultdict(int)
    dp[0] = 1
    prefix_sum[0] = 1

    for i in range(1, len(classes)):
        start = classes[i][0]
        best = bin_search(classes, start)
        dp[i] = 1 + prefix_sum[best]
        prefix_sum[i] = dp[i] + prefix_sum[i-1]
    return sum(dp)


def format_ans(ans):
    s = str(ans)
    if len(s) >= 8:
        return s[len(s)-8:]
    else:
        return (8-len(s)) * "0" + s


while True:
    n = int(input())
    classes = []
    if n == - 1:
        break

    for _ in range(n):
        start, end = map(int, input().split())
        classes.append((start, end))

    ans = num_nonoverlapping(classes)
    print(format_ans(ans))

I’m getting a Time Limit Exceeded Error. I'd love some pointers on how I could make this faster.

Answer 1

Disclaimer: I write the review as I go - I haven't performed any optimisation yet but this may be useful to you or other reviewers.

Your code is well organised, having the actual algorithm in a function on its own, away from the logic handling input/ouput. This is a great habit (usually not done properly for programming challenges) and is much appreciated :-)

Adding tests

Before doing any changes to your code, I'd rather start by writing a few tests. This can also be useful later on to use them for benchmarks and check that optimisations do make things faster.

Here, this is an easy task because of the way you've written the code and because examples are provided.

I tend not to bother with unit-tests frameworks for such small tasks but this is a good occasion to give them a try if needed.

def unit_tests_num_nonoverlapping():
    classes, exp = [(1, 3), (3, 5), (5, 7), (2, 4), (4, 6)], 12
    ans = num_nonoverlapping(classes)
    assert ans == exp
    classes, exp = [(500000000, 1000000000), (1, 500000000), (1, 500000000)], 5 
    ans = num_nonoverlapping(classes)
    assert ans == exp
    classes, exp = [(999999999, 1000000000)], 1
    ans = num_nonoverlapping(classes)
    assert ans == exp


def unit_tests_format_ans():
    assert "00000000" == format_ans(0)
    assert "00000005" == format_ans(5)
    assert "00000054" == format_ans(54)
    assert "00000540" == format_ans(540)
    assert "00005400" == format_ans(5400)
    assert "00054000" == format_ans(54000)
    assert "00540000" == format_ans(540000)
    assert "05400000" == format_ans(5400000)
    assert "54000000" == format_ans(54000000)
    assert "40000000" == format_ans(540000000)
    assert "00000000" == format_ans(5400000000)

def unit_tests():
    unit_tests_num_nonoverlapping()
    unit_tests_format_ans()


def io_test():
    while True:
        n = int(input())
        classes = []
        if n == - 1:
            break

        for _ in range(n):
            start, end = map(int, input().split())
            classes.append((start, end))

        ans = num_nonoverlapping(classes)
        print(format_ans(ans))


unit_tests()
# io_tests()

Improving format_ans

This is most probably not the place where we can get much performance improvements but it is a good place to learn a few additional techniques.

First thing I did was to define the number of digits wanted as a argument with default value 8 so that we do not break already existing behavior but we do get rid of the "8" magic number everywhere.

Using modulo, you can get the last 8 digits without getting into string manipulation.

def format_ans(ans, nb_dig=8):
    s = str(ans % 10**nb_dig)
    return (nb_dig-len(s)) * "0" + s

Python already defines a few builtin functions which you can use for a more concise solution. Here, we could use: str.zfill:

def format_ans(ans, nb_dig=8):
    return str(ans % 10**nb_dig).zfill(nb_dig)

You could probably use other string formatting functions but I think this is explicit enough.

Improving num_nonoverlapping

Due to the limits provided by the problem description, we have to expect a huge numbers of classes. This means that a fast solution will probably come from a great algorithm rather than micro-optimisations.

Your algorithm seems good.

At the moment, I have nothing better to suggest.