Dominos Pizza has hungry customers waiting in the queue. Each unique order is placed by a customer at time x[i], and the order takes y[i] units of time to complete.
You have information on all n orders, Find the order in which all customers will receive their pizza and return it. If two or more orders are completed at the same time then sort them by non-decreasing order number.
Example 1:
Input : arr[ ] = {{4,1}, {6,2}, {7,6}, 
                       {8,1}, {1,3}}
Output : 5 1 2 4 3
Explanation:
Here an array can be transform to 
{5, 8, 13, 9, 4}. Here 5^{th} index order 
received first then 1^{st} order, 2^{nd} order...
return {5, 1, 2, 4, 3}
Example 2:
Input : arr[ ] = {{1,1}, {1,1}, {1,1}} 
Output :  1 2 3 
 
Your Task:
This is a function problem. The input is already taken care of by the driver code. You only need to complete the function permute() that takes 2-d array (arr), sizeOfArray (n), and return the array of order in which customers will receive their pizza. The driver code takes care of the printing.
Expected Time Complexity: O(N*LOG(N)).
Expected Auxiliary Space: O(N).
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ arr[i][0], arr[i][1] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: EASY
Tags: Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def permute(self,arr,n):

        #Complete the function



Solutions:
class Solution:

	def permute(self, arr, n):
		d = []
		for i in range(0, n):
			(a, b) = arr[i]
			d.append([a + b, i])
		d.sort()
		res = []
		for k in d:
			res.append(k[1] + 1)
		return res


class Solution:

	def permute(self, arr, n):
		endTime = [(arr[i][0] + arr[i][1], i + 1) for i in range(len(arr))]
		endTime.sort()
		ans = [x[1] for x in endTime]
		return ans


from collections import OrderedDict

class Solution:

	def permute(self, arr, n):
		res = [i[0] + i[1] for i in arr]
		ind = [i + 1 for i in range(len(arr))]
		d = OrderedDict(zip(ind, res))
		res = list(OrderedDict(sorted(d.items(), key=lambda x: x[1])))
		return res


class Solution:

	def permute(self, arr, n):
		di = {}
		l = []
		for i in range(len(arr)):
			di[i] = arr[i][0] + arr[i][1]
		x = sorted(di.items(), key=lambda kv: kv[1])
		for i in x:
			l.append(i[0] + 1)
		return l


class Solution:

	def permute(self, arr, n):
		vals = []
		for i in range(len(arr)):
			vals.append([i, arr[i][0] + arr[i][1]])
		vals = sorted(vals, key=lambda x: x[1])
		value = []
		for i in vals:
			value.append(i[0] + 1)
		return value


class Solution:

	def permute(self, arr, n):
		for i in range(len(arr)):
			arr[i][1] = arr[i][0] + arr[i][1]
			arr[i][0] = i + 1
		arr.sort(key=lambda x: (x[1], x[0]))
		return [i[0] for i in arr]


class Solution:

	def permute(self, arr, n):
		l = []
		for (i, j) in arr:
			l.append(i + j)
		d = {}
		arr = sorted(l)
		for i in range(len(arr)):
			if l[i] in d:
				d[l[i]].append(i + 1)
			else:
				d[l[i]] = [i + 1]
		for i in range(len(l)):
			l[i] = d[arr[i]][0]
			if len(d[arr[i]]) > 1:
				d[arr[i]].pop(0)
		return l


class Solution:

	def permute(self, arr, n):
		order = []
		for i in range(n):
			order.append([arr[i][0] + arr[i][1], i])
		order = sorted(order, key=lambda x: x[0])
		return [i[1] + 1 for i in order]


class Solution:

	def permute(self, arr, n):
		smallAns = []
		for i in range(n):
			smallAns.append([arr[i][0] + arr[i][1], i])
		smallAns = sorted(smallAns, key=lambda x: x[0])
		finalAns = []
		for ele in smallAns:
			finalAns.append(ele[1] + 1)
		return finalAns


class Solution:

	def permute(self, arr, n):
		dict = {}
		li = []
		for i in range(len(arr)):
			dict[i] = arr[i][0] + arr[i][1]
		sorted_x = sorted(dict.items(), key=lambda kv: kv[1])
		for i in sorted_x:
			li.append(i[0] + 1)
		return li


class Solution:

	def permute(self, arr, n):
		arr = [[arr[i][0] + arr[i][1], i] for i in range(n)]
		s = sorted(arr, key=lambda x: x[0])
		return [k + 1 for (i, k) in s]


class Solution:

	def permute(self, arr, n):
		ar = []
		i = 1
		for el in arr:
			sum = el[0] + el[1]
			ar.append([sum, i])
			i += 1
		ans = []
		ar.sort()
		for el in ar:
			ans.append(el[1])
		return ans


class Solution:

	def permute(self, arr, n):
		l = []
		ans = []
		for i in range(n):
			l.append([arr[i][0] + arr[i][1], i + 1])
		l.sort(key=lambda x: x[0])
		for i in range(n):
			ans.append(l[i][1])
		return ans


class Solution:

	def permute(self, arr, n):
		s = []
		ans = []
		for i in range(len(arr)):
			s.append([sum(arr[i]), i + 1])
		s.sort(key=lambda x: x[0])
		for i in range(len(s)):
			ans.append(s[i][1])
		return ans


class Solution:

	def permute(self, arr, n):
		orders = [[sum(arr[i]), i + 1] for i in range(n)]
		orders.sort()
		return [item[1] for item in orders]


class Solution:

	def permute(self, arr, n):
		l = []
		for i in range(n):
			l.append([arr[i][0] + arr[i][1], i + 1])
		l.sort()
		r = []
		for i in range(n):
			r.append(l[i][1])
		return r


class Solution:

	def permute(self, arr, n):
		l = []
		for i in range(n):
			s = sum(arr[i])
			l.append([s, i])
		l.sort()
		r = []
		for i in range(n):
			c = l[i][1]
			r.append(c + 1)
		return r


class Solution:

	def permute(self, arr, n):
		ls = []
		for x in arr:
			ls.append(sum(x))
		k = {}
		for i in range(len(ls)):
			if ls[i] in k.keys():
				k[ls[i]].append(i + 1)
			else:
				k[ls[i]] = [i + 1]
		ss = list(set(ls))
		ss.sort()
		res = []
		for x in ss:
			temp = k[x]
			temp.sort()
			res += temp
		return res


class Solution:

	def permute(self, arr, n):

		def index(ele):
			return ele[0]
		for i in range(n):
			arr[i][0] = arr[i][0] + arr[i][1]
		for (count, ele) in enumerate(arr):
			ele[1] = count + 1
		arr.sort(key=index)
		for i in range(n):
			arr[i] = arr[i][1]
		return arr


class Solution:

	def permute(self, arr, n):
		return [idx for (_, idx) in sorted(((start + end, i) for (i, (start, end)) in enumerate(arr, start=1)))]


class Solution:

	def permute(self, arr, n):
		d = {}
		for i in range(n):
			a = sum(arr[i])
			b = i + 1
			if a not in d:
				d[a] = [b]
			else:
				d[a].append(b)
		x = []
		for i in d:
			x.append(i)
		x.sort()
		ans = []
		for i in x:
			c = d[i]
			c.sort()
			for j in c:
				ans.append(j)
		return ans


class Solution:

	def permute(self, arr, n):
		time = [sum(x) for x in arr]
		dis = {}
		i = 1
		for x in time:
			dis[i] = x
			i += 1
		res = [x[0] for x in sorted(dis.items(), key=lambda dis: dis[1])]
		return res


class Solution:

	def permute(self, arr, n):
		temp = []
		ans = []
		for i in range(n):
			ans.append([arr[i][0] + arr[i][1], i + 1])
		ans.sort()
		final = []
		for i in ans:
			final.append(i[-1])
		return final


class Solution:

	def permute(self, a, n):
		temp = []
		for i in range(n):
			temp.append([a[i][0] + a[i][1], i + 1])
		temp.sort()
		l = []
		for i in range(n):
			l.append(temp[i][1])
		return l


class Solution:

	def permute(self, arr, n):
		hashmap = {}
		ans = [0] * n
		for i in range(n):
			res = arr[i][0] + arr[i][1]
			hashmap[i] = res
		lst = sorted(hashmap.items(), key=lambda x: x[1])
		for i in range(n):
			ans[i] = lst[i][0] + 1
		return ans


class Solution:

	def permute(self, arr, n):
		l = []
		for i in range(n):
			l.append([arr[i][0] + arr[i][1], i + 1])
		l.sort()
		p = []
		for i in range(n):
			p.append(l[i][1])
		return p
for _ in range(0, int(input())):
	n = int(input())
	arr = []
	for _ in range(0, n):
		ll = list(map(int, input().strip().split()))
		arr.append(ll)
	obj = Solution()
	ans = obj.permute(arr, n)
	for i in ans:
		print(i)


class Solution:

	def permute(self, arr, n):
		(a, b) = zip(*arr)
		d = []
		c = list(map(lambda x, y: x + y, a, b))
		for i in range(n):
			d.append(i + 1)
		e = list(zip(c, d))
		e.sort(key=lambda x: x[0])
		(a, b) = zip(*e)
		return b
for _ in range(0, int(input())):
	n = int(input())
	arr = []
	for _ in range(0, n):
		ll = list(map(int, input().strip().split()))
		arr.append(ll)
	obj = Solution()
	ans = obj.permute(arr, n)
	for i in ans:
		print(i)


class Solution:

	def permute(self, arr, n):
		for i in range(n):
			arr[i] = [sum(arr[i]), i + 1]
		c = sorted(arr)
		ans = []
		for i in c:
			ans.append(i[1])
		return ans
for _ in range(0, int(input())):
	n = int(input())
	arr = []
	for _ in range(0, n):
		ll = list(map(int, input().strip().split()))
		arr.append(ll)
	obj = Solution()
	ans = obj.permute(arr, n)
	for i in ans:
		print(i)


class Solution:

	def permute(self, arr, n):
		return [idx for (_, idx) in sorted(((start + end, i) for (i, (start, end)) in enumerate(arr, start=1)))]
for _ in range(0, int(input())):
	n = int(input())
	arr = []
	for _ in range(0, n):
		ll = list(map(int, input().strip().split()))
		arr.append(ll)
	obj = Solution()
	ans = obj.permute(arr, n)
	for i in ans:
		print(i)


class Solution:

	def permute(self, arr, n):
		for i in range(n):
			arr[i] = [sum(arr[i]), i + 1]
		c = sorted(arr)
		ans = []
		for i in c:
			ans.append(i[1])
		return ans


class Solution:

	def permute(self, arr, n):
		return [j for (i, j) in sorted(((p + q, i) for (i, (p, q)) in enumerate(arr, 1)))]


class Solution:

	def permute(self, a, n):
		a = [sum(i) for i in a]
		l = list(enumerate(a))
		l.sort(key=lambda x: x[1])
		for i in range(n):
			a[i] = l[i][0] + 1
		return a


class Solution:

	def permute(self, arr, n):
		lis = []
		for i in range(n):
			lis.append((arr[i][0] + arr[i][1], i + 1))
		lis.sort(key=lambda x: x[0])
		res = []
		for i in lis:
			res.append(i[1])
		return res


class Solution:

	def permute(self, arr, n):
		sortlist = {}
		for i in range(n):
			sortlist[i + 1] = arr[i][0] + arr[i][1]
		sorted_dt_value = sorted(sortlist.items(), key=lambda item: item[1])
		listarr = []
		for i in range(n):
			listarr.append(sorted_dt_value[i][0])
		return listarr


class Solution:

	def permute(self, arr, n):
		res = []
		add = 0
		for i in range(0, len(arr)):
			add = add + (arr[i][0] + arr[i][1])
			res.append([add, i + 1])
			add = 0
		res.sort()
		return [res[i][1] for i in range(0, n)]


class Solution:

	def permute(self, arr, n):
		t = [[v[0] + v[1], i] for (i, v) in enumerate(arr, start=1)]
		t.sort()
		return [order[1] for order in t]


class Solution:

	def permute(self, arr, n):
		l1 = []
		l2 = []
		for i in range(0, n):
			l1.append([arr[i][0] + arr[i][1], i + 1])
		l1.sort()
		for i in range(0, n):
			l2.append(l1[i][1])
		return l2


class Solution:

	def permute(self, arr, n):
		new_arr = []
		for i in range(n):
			new_arr.append((arr[i][0] + arr[i][1], i))
		new_arr.sort()
		results = [x[1] + 1 for x in new_arr]
		return results


class Solution:

	def permute(self, arr, n):
		arr = [(_[0] + _[1], i) for (i, _) in enumerate(arr)]
		arr.sort()
		results = []
		for _ in arr:
			results.append(_[1] + 1)
		return results


class Solution:

	def permute(self, arr, n):
		l = []
		k = []
		for i in range(n):
			l.append([arr[i][0] + arr[i][1], i + 1])
		l = sorted(l)
		for i in range(n):
			k.append(l[i][1])
		return k


class Solution:

	def permute(self, arr, n):
		return [ans[1] for ans in sorted(((arr[i][0] + arr[i][1], i + 1) for i in range(n)))]


class Solution:

	def permute(self, arr, n):
		time_arr = []
		i = 1
		for order in arr:
			time_arr.append([order[0] + order[1], i])
			i += 1
		time_arr = sorted(time_arr, key=lambda x: x[0])
		ind_arr = []
		for ind in time_arr:
			ind_arr.append(ind[1])
		return ind_arr


class Elem:

	def __init__(self, val, i):
		self.val = val
		self.ind = i

def takeVal(el):
	return el.val

def checkInd(arr, n):
	ind_last = -100
	i = 0
	changed_i = False
	while i < n - 1:
		changed_i = False
		if arr[i].val == arr[i + 1].val and arr[i].ind > arr[i + 1].ind:
			tmp = arr[i]
			arr[i] = arr[i + 1]
			arr[i + 1] = tmp
			if ind_last != -100:
				if arr[ind_last].val == arr[i + 1].val:
					changed_i = True
					i = ind_last
			ind_last = i
		if not changed_i:
			i += 1
	return arr

class Solution:

	def permute(self, arr, n):
		aux_arr = []
		for i in range(n // 2 + 1):
			if i < n - 1 - i:
				aux_arr.append(Elem(arr[i][0] + arr[i][1], i))
				aux_arr.append(Elem(arr[n - 1 - i][0] + arr[n - 1 - i][1], n - 1 - i))
			elif i == n - 1 - i:
				aux_arr.append(Elem(arr[i][0] + arr[i][1], i))
		aux_arr.sort(key=takeVal)
		aux_arr = checkInd(aux_arr, n)
		aux_arr1 = [x.ind + 1 for x in aux_arr]
		return aux_arr1


class Solution:

	def permute(self, arr, n):
		ans = []
		for i in range(n):
			su = sum(arr[i])
			ans.append([su, i])
		ans.sort()
		rans = []
		for i in range(n):
			catch = ans[i][1]
			rans.append(catch + 1)
		return rans


class Solution:

	def permute(self, arr, n):
		q = []
		for i in range(n):
			q.append([i + 1, arr[i][0] + arr[i][1]])
		q.sort(key=lambda x: x[1])
		res = []
		for (idx, val) in q:
			res.append(idx)
		return res


class Solution:

	def permute(self, arr, n):
		d = {}
		for i in range(0, n):
			d[i + 1] = arr[i][0] + arr[i][1]
		l = [k for (k, v) in sorted(d.items(), key=lambda item: item[1])]
		return l


class Solution:

	def permute(self, arr, n):
		return [index for (_, index) in sorted(((start + end, j) for (j, (start, end)) in enumerate(arr, start=1)))]


class Solution:

	def permute(self, arr, n):
		for i in range(n):
			arr[i] = [arr[i][0] + arr[i][1], i + 1]
		arr.sort()
		for i in range(n):
			arr[i] = arr[i][1]
		return arr


class Solution:

	def permute(self, arr, n):
		order_hash = {}
		min_add = 0
		max_add = 0
		x = 0
		for orders in arr:
			add = orders[0] + orders[1]
			min_add = min(min_add, add)
			max_add = max(max_add, add)
			if add in order_hash:
				orders.append(x + 1)
				order_hash[add].append(orders)
			else:
				orders.append(x + 1)
				order_hash[add] = [orders]
			x += 1
		fin_arr = []
		for key in range(min_add, max_add + 1):
			if key in order_hash:
				if len(order_hash[key]) == 1:
					fin_arr.append(order_hash[key][0][2])
				else:
					arr = order_hash[key]
					arr = sorted(arr, key=lambda y: y[2])
					for orders in arr:
						fin_arr.append(orders[2])
		return fin_arr


class Solution:

	def permute(self, arr, n):
		l = []
		a = []
		for i in range(len(arr)):
			l.append((sum(arr[i]), i + 1))
		l.sort(key=lambda x: x[0])
		for i in range(len(l)):
			a.append(l[i][1])
		return a


class Solution:

	def permute(self, arr, n):
		s = sorted(enumerate(arr, 1), key=lambda x: sum(x[1]))
		return [i[0] for i in s]


class Solution:

	def permute(self, arr, n):
		a = sorted(((arr[i][0] + arr[i][1], i) for i in range(len(arr))))
		return [x[1] + 1 for x in a]


class Solution:

	def permute(self, arr, n):
		lst2 = []
		lst = []
		for i in range(n):
			x = arr[i][0] + arr[i][1]
			lst.append([x, i])
		lst.sort()
		for elt in lst:
			lst2.append(elt[1] + 1)
		return lst2


class Solution:

	def permute(self, a, n):
		for i in range(n):
			a[i][1] += a[i][0]
			a[i].append(i + 1)

		def key(a):
			return a[1]
		a.sort(key=key)
		ans = [i[2] for i in a]
		return ans


import heapq

class Solution:

	def permute(self, arr, n):
		order = []
		for (idx, time) in enumerate(arr):
			order.append([time[0] + time[1], idx])
		heapq.heapify(order)
		ans = []
		while order:
			(_, idx) = heapq.heappop(order)
			ans.append(idx + 1)
		return ans


import heapq

class Solution:

	def permute(self, arr, n):
		order = []
		for (idx, time) in enumerate(arr):
			order.append([time[0] + time[1], idx])
		ans = []
		order.sort()
		for (_, idx) in order:
			ans.append(idx + 1)
		return ans


class Solution:

	def permute(self, arr, n):
		ar = []
		for i in range(n):
			ar.append([arr[i][0] + arr[i][1], i])
		ar = sorted(ar, key=lambda a: a[0])
		res = []
		for i in range(n):
			res.append(ar[i][1] + 1)
		return res