My take on the algorithmic crush problem from HackerRank

Question

This is my solution to the Algorithmic Crush problem from HackerRank. Can I get any comments regarding where I can improve the code to be more efficient?

You are given a list of size \$N\,ドル initialized with zeroes. You have to perform \$M\$ operations on the list and output the maximum of final values of all the \$N\$ elements in the list. For every operation, you are given three integers \$a, b\$ and \$k\$ and you have to add value to all the elements ranging from index \$a\$ to \$b\$ (both inclusive).

Input Format

First line will contain two integers \$N\$ and \$M\$ separated by a single space. Next \$M\$ lines will contain three integers \$a, b\$ and \$k\$ separated by a single space. Numbers in list are numbered from \1ドル\$ to \$N\$.

Constraints

\3ドル \leq N \leq 10^7\$

\1ドル\leq M \leq 2*10^5\$

\1ドル \leq a \leq b \leq N\$

\$ 0 \leq k \leq 10^9\$

Output Format

A single line containing maximum value in the updated list.

Sample Input

5 3
1 2 100
2 5 100
3 4 100

Sample Output

200

def updateList(seq, listA):
 st, end, value = map(int, seq.split())
 for i in range(st-1, end):
 listA[i] = listA[i]+value
 return listA
n, m = map(int, raw_input().split())
lis = [0 for i in range(n)]
for ins in range(m):
 cmds = raw_input()
 resultSet = updateList(cmds, lis)
 lis = resultSet
print sorted(resultSet)[-1]

• CiaPan: I think the biggest improvement (to the question, not to the code) would be adding a problem statement.

Answer 1

The code is generally clean, however, maintaining the same algorithm will probably result in a timeout for this problem. Your current complexity is \$ O(N\cdot M) \$ which could be up to \$ 10^7 \times 10^5 \$ according to the problem statement.

A similar problem to this is the maximum interval overlap problem, discussed here. The problem is given the guest arrival and departure times in a party, find the interval with the maximum guests. It should be a good exercise to apply the same idea to this problem.

• Christoph: It's basically a 1D collision detection. The article you link uses sweep and prune to solve it. It is a very good read but if one needs further reading: There are a lot of articles on sweep and prune on the web.