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↵
↵
↵
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↵
↵
