Given an array arr of size N with all initial values as 0, the task is to perform the following M range increment operations as shown below: 
Increment(a_{i}, b_{i}, k_{i}) : Increment values from index 'a_{i}' to 'b_{i}' by 'k_{i}'.
After M operations, calculate the maximum value in the array arr[].
Example 1:
Input: N = 5, M = 3, a[] = {0, 1, 2}
b[] = {1, 4, 3}, k[] = {100, 100, 100}
Output: 200
Explanation: Initially array = {0, 0, 0, 
                                   0, 0}
After first operation : {100, 100, 0, 0, 0}
After second operation: {100, 200, 100, 100, 100}
After third operation: {100, 200, 200, 200, 100}
Maximum element after m operations is 200.
Example 2:
Input: N = 4, M = 3, a[] = {1, 0, 3} 
b[] = {2, 0, 3}, k[] = {603, 286, 882}
Output: 882
Explanation: Initially array = {0, 0, 0, 0}
After first operation: {0, 603, 603, 0}
After second operation: {286, 603, 603, 0}
After third operation: {286, 603, 603, 882}
Maximum element after m operations is 882.
Your Task:
You don't need to read input or print anything. You just need to complete the function findMax() that takes arrays a[], b[], k[] and integers N, M as parameters and returns the desired output.
 
Expected Time Complexity: O(M+N).
Expected Auxiliary Space: O(N).
 
Constraints:
1 ≤ N ≤ 10^{6}
0 ≤ a_{i } ≤ b_{i} ≤ N-1
1 ≤ M ≤ 10^{6}
0 ≤ k_{i} ≤ 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Range queries

Data structures

Mathematics

Starter code: class Solution:
    def findMax(self,n, m,a, b, c):
        # Your code goes here

Solutions:
class Solution:

	def findMax(self, n, m, a, b, c):
		ans = [0] * (n + 1)
		for i in range(m):
			ans[a[i]] += c[i]
			ans[b[i] + 1] -= c[i]
		for i in range(1, n + 1):
			ans[i] += ans[i - 1]
		return max(ans)


class Solution:

	def findMax(self, n, m, a, b, c):
		db = {}
		de = {}
		for i in range(m):
			if a[i] not in db.keys():
				db[a[i]] = c[i]
			else:
				db[a[i]] += c[i]
			if b[i] not in de.keys():
				de[b[i]] = c[i]
			else:
				de[b[i]] += c[i]
		ans = []
		x = 0
		for i in range(n):
			if i in db.keys():
				x += db[i]
			ans.append(x)
			if i in de.keys():
				x -= de[i]
		return max(ans)


class Solution:

	def findMax(self, n, m, a, b, c):
		d = dict()
		for i in range(n + 1):
			d[i] = 0
		for i in range(m):
			d[a[i]] = d[a[i]] + c[i]
			d[b[i] + 1] = d[b[i] + 1] - c[i]
		m = 0
		s = 0
		for i in range(n):
			if d.get(i) != None:
				s = s + d[i]
				m = max(m, s)
		return m


class Solution:

	def findMax(self, n, m, a, b, k):
		l = [0] * (n + 1)
		for i in range(m):
			l[a[i]] += k[i]
			l[b[i] + 1] -= k[i]
		for i in range(1, len(l)):
			l[i] = l[i] + l[i - 1]
		return max(l)


class Solution:

	def findMax(self, n, m, a, b, c):
		arr = [0] * n
		for i in range(m):
			x = a[i]
			y = b[i]
			arr[x] += c[i]
			if y + 1 != n:
				arr[y + 1] += -c[i]
		pre = 0
		for i in range(n):
			pre += arr[i]
			arr[i] = pre
		return max(arr)


class Solution:

	def findMax(self, n, m, a, b, c):
		arr = [0] * (n + 2)
		for i in range(m):
			arr[a[i]] += c[i]
			arr[b[i] + 1] -= c[i]
		mx = arr[0]
		for i in range(1, n):
			arr[i] += arr[i - 1]
			mx = max(mx, arr[i])
		return mx


class Solution:

	def findMax(self, n, m, a, b, c):
		ques = [0 for i in range(n)]
		for i in range(m):
			(l, r, cost) = (a[i], b[i], c[i])
			ques[l] += cost
			if r + 1 < n:
				ques[r + 1] -= cost
		res = [ques[0]]
		ans = ques[0]
		for i in range(1, n):
			ans = max(ans, res[-1] + ques[i])
			res.append(res[-1] + ques[i])
		return ans


class Solution:

	def findMax(self, n, m, a, b, c):
		rec = [0] * n
		for i in range(m):
			rec[b[i]] += c[i]
			if a[i] > 0:
				rec[a[i] - 1] -= c[i]
		ac = 0
		for i in range(n - 1, -1, -1):
			ac += rec[i]
			rec[i] = ac
		return max(rec)


class Solution:

	def findMax(self, n, m, a, b, k):
		arr = [0] * (n + 1)
		for i in range(m):
			arr[a[i]] += k[i]
			arr[b[i] + 1] -= k[i]
		s = 0
		res = 0
		for i in range(n):
			s += arr[i]
			res = max(res, s)
		return res


class Solution:

	def findMax(self, n, m, a, b, c):
		arr = [0] * n
		for i in range(m):
			arr[a[i]] += c[i]
			if b[i] + 1 < n:
				arr[b[i] + 1] -= c[i]
		res = arr[0]
		for i in range(1, n):
			arr[i] += arr[i - 1]
			res = max(res, arr[i])
		return res


import sys

class Solution:

	def findMax(self, n, m, a, b, k):
		arr = [0 for i in range(n + 1)]
		for i in range(m):
			lowerbound = a[i]
			upperbound = b[i]
			arr[lowerbound] += k[i]
			arr[upperbound + 1] -= k[i]
		sum = 0
		res = -1 - sys.maxsize
		for i in range(n):
			sum += arr[i]
			res = max(res, sum)
		return res


class Solution:

	def findMax(self, n, m, a, b, c):
		arr = [0] * n
		for i in range(m):
			arr[a[i]] += c[i]
			if b[i] < len(arr) - 1:
				arr[b[i] + 1] -= c[i]
		maxa = 0
		suma = 0
		for i in range(n):
			suma += arr[i]
			maxa = max(suma, maxa)
		return maxa


class Solution:

	def findMax(self, n, m, a, b, c):
		ans = [0] * n
		for i in range(m):
			ans[a[i]] += c[i]
			if b[i] + 1 < n:
				ans[b[i] + 1] -= c[i]
		m = ans[0]
		for i in range(1, n):
			ans[i] = ans[i] + ans[i - 1]
		return max(ans)
if __name__ == '__main__':
	t = int(input())
	for _ in range(0, t):
		l = list(map(int, input().split()))
		n = l[0]
		m = l[1]
		a = []
		b = []
		c = []
		for j in range(0, m):
			v = list(map(int, input().split()))
			a.append(v[0])
			b.append(v[1])
			c.append(v[2])
		ob = Solution()
		print(ob.findMax(n, m, a, b, c))


class Solution:

	def findMax(self, n, m, a, b, c):
		ls = [0] * n
		for i in range(m):
			ls[a[i]] += c[i]
			if b[i] + 1 < len(ls):
				ls[b[i] + 1] -= c[i]
		sumi = ls[0]
		for i in range(1, len(ls)):
			sumi += ls[i]
			ls[i] = sumi
		return max(ls)


from operator import add

class Solution:

	def findMax(self, n, m, a, b, c):
		l = [0] * 10 ** 6
		for i in range(0, m):
			l[a[i]] += c[i]
			l[b[i] + 1] -= c[i]
		for i in range(1, n):
			l[i] = l[i] + l[i - 1]
		return max(l)


class Solution:

	def findMax(self, n, m, a, b, c):
		arr = [[] for i in range(n)]
		li = [0 for i in range(n)]
		for i in range(m):
			arr[a[i]].append([c[i], 0])
			arr[b[i]].append([c[i], 1])
		x = 0
		for i in range(n):
			s = e = 0
			for (k, l) in arr[i]:
				if l == 0:
					s += k
				else:
					e += k
			li[i] = x + s
			x += s - e
		return max(li)


class Solution:

	def findMax(self, n, m, a, b, c):
		ans = [0 for i in range(n + 1)]
		for i in range(m):
			lowerbound = a[i]
			upperbound = b[i]
			ans[lowerbound] += c[i]
			ans[upperbound + 1] -= c[i]
		maxsum = ans[0]
		for i in range(1, n):
			ans[i] += ans[i - 1]
			if maxsum < ans[i]:
				maxsum = ans[i]
		return maxsum


class Solution:

	def findMax(self, n, m, a, b, c):
		d = [0] * n
		maxEle = 0
		for i in range(m):
			d[a[i]] += c[i]
			if b[i] + 1 < n:
				d[b[i] + 1] -= c[i]
		sumSoFar = 0
		for i in range(n):
			sumSoFar += d[i]
			d[i] = sumSoFar
		maxEle = 0
		for i in d:
			if i > maxEle:
				maxEle = i
		return maxEle


class Solution:

	def findMax(self, n, m, a, b, c):
		arr = [0 for i in range(n + 1)]
		for x in range(m):
			(left, right, val) = (a[x], b[x], c[x])
			arr[left] += val
			arr[right + 1] -= val
		for i in range(1, n + 1):
			arr[i] += arr[i - 1]
		return max(arr)


class Solution:

	def findMax(self, n, m, a, b, c):
		arr = [0 for i in range(n)]
		for i in range(m):
			(l, r, val) = (a[i], b[i], c[i])
			arr[l] += val
			if r + 1 < n:
				arr[r + 1] -= val
		for i in range(1, n):
			arr[i] += arr[i - 1]
		return max(arr)


class Solution:

	def findMax(self, n, m, a, b, c):
		res = [0] * (n + 1)
		for i in range(m):
			i1 = a[i]
			i2 = b[i]
			val = c[i]
			res[i1] += val
			res[i2 + 1] -= val
		maximum = res[0]
		for i in range(1, n):
			res[i] += res[i - 1]
			maximum = max(maximum, res[i])
		return maximum