There are N ticket sellers where the ith ticket seller has A[i] tickets. 
The price of a ticket is the number of tickets remaining with the ticket seller. They are allowed to sell at most K tickets. Find the maximum amount they can earn by selling K tickets. 
The amount of tickets of each seller is provided in array A. Give the answer modulo 10^{9} + 7.
Example 1:
Input: N = 5, K = 3
A = {4, 3, 6, 2, 4}
Output: 15
Explaination: Consider 0 based indexing. 
For first two turns the 2nd seller sells. 
For the third turn either 0th or 2nd 
seller can sell. So the total becomes 
6 + 5 + 4 = 15.
Example 2:
Input: N = 6, K = 2
A = {5, 3, 5, 2, 4, 4}
Output: 10
Explaination: The turns are taken by 
0th and 2nd seller. 5 + 5 = 10 is the 
maximum amount.
Your Task:
You do not need to take input or print anything. Your task is to complete the function maxAmount() which takes N, K, and the array A as input parameters and returns the maximum amount they can get by selling K tickets.
Expected Time Complexity: O(N*log(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ A[i], K ≤ 10^{6}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Starter code: #User function Template for python3



class Solution:

    def maxAmount(self, N, K, A):

        # code here

Solutions:
import heapq

class Solution:

	def maxAmount(self, N, K, A):
		h = []
		heapq.heapify(h)
		for i in range(len(A)):
			heapq.heappush(h, -int(A[i]))
		res = 0
		M = 10 ** 9 + 7
		while K > 0:
			t = heapq.heappop(h)
			res = (res % M + -t % M) % M
			heapq.heappush(h, -(-t - 1))
			K -= 1
		return res % M


import heapq

def fn(K, arr):
	arr = [-arr[i] for i in range(N)]
	heapq.heapify(arr)
	res = 0
	while K:
		x = abs(heapq.heappop(arr))
		res += x
		heapq.heappush(arr, -(x - 1))
		K -= 1
	return res % 1000000007

class Solution:

	def maxAmount(self, N, K, A):
		return fn(K, A)


from heapq import heappop, heappush, heapify

class Solution:

	def maxAmount(self, N, K, A):
		ans = 0
		MaxHeap = []
		for i in range(N):
			heappush(MaxHeap, A[i] * -1)
		for i in range(K):
			max_amount = heappop(MaxHeap)
			ans += -1 * max_amount
			heappush(MaxHeap, max_amount + 1)
		return ans % (10 ** 9 + 7)


import heapq as h

class Solution:

	def maxAmount(self, N, K, A):
		hp = []
		h.heapify(hp)
		for i in range(N):
			h.heappush(hp, -1 * A[i])
		ans = 0
		for i in range(K):
			x = h.heappop(hp)
			ans += -1 * x
			h.heappush(hp, x + 1)
		return ans % 1000000007


from heapq import heappop, heappush, heapify

class Solution:

	def maxAmount(self, N, K, A):
		heap = []
		heapify(heap)
		for a in A:
			heappush(heap, -1 * int(a))
		tot = 0
		for i in range(K):
			e = -1 * heappop(heap)
			tot += e
			heappush(heap, -1 * (e - 1))
		return tot % (10 ** 9 + 7)