Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years. ×

Python TLE for Actiities (Spoj)

Revision en1, by pfft, 2019-12-13 21:38:34

I am trying to sovle this question: https://www.spoj.com/problems/ACTIV/

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 TLE :frowning: I’d love some pointers on how I could make this faster

#### History

Revisions

Rev. Lang. By When Δ Comment
en2 pfft 2019-12-13 21:39:03 1
en1 pfft 2019-12-13 21:38:34 1444 Initial revision (published)