Given a set of N jobs where each job_{i} has a deadline and profit associated with it. 
Each job takes 1 unit of time to complete and only one job can be scheduled at a time. We earn the profit associated with job if and only if the job is completed by its deadline. 
Find the number of jobs done and the maximum profit.
Note: Jobs will be given in the form (Job_{id}, Deadline, Profit) associated with that Job.
Example 1:
Input:
N = 4
Jobs = {(1,4,20),(2,1,10),(3,1,40),(4,1,30)}
Output:
2 60
Explanation:
Job_{1} and Job_{3 }can be done with
maximum profit of 60 (20+40).
Example 2:
Input:
N = 5
Jobs = {(1,2,100),(2,1,19),(3,2,27),
        (4,1,25),(5,1,15)}
Output:
2 127
Explanation:
2 jobs can be done with
maximum profit of 127 (100+27).
Your Task :
You don't need to read input or print anything. Your task is to complete the function JobScheduling() which takes an integer N and an array of Jobs(Job id, Deadline, Profit) as input and returns the count of jobs and maximum profit as a list or vector of 2 elements.
Expected Time Complexity: O(NlogN)
Expected Auxilliary Space: O(N)
Constraints:
1 <= N <= 10^{5}
1 <= Deadline <= N
1 <= Profit <= 500

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Dynamic programming

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    

    #Function to find the maximum profit and the number of jobs done.

    def JobScheduling(self,Jobs,n):

        

        # code here

Solutions:
class Solution:

	def JobScheduling(self, Jobs, n):
		max_d = max({x.deadline for x in Jobs})
		Jobs.sort(key=lambda x: -x.profit)
		dp = [0] * max_d
		for i in range(len(Jobs)):
			for j in range(min(max_d - 1, Jobs[i].deadline - 1), -1, -1):
				if dp[j] == 0:
					dp[j] = Jobs[i].profit
					break
		(jobs_done, max_p) = (0, 0)
		for p in dp:
			if p > 0:
				jobs_done += 1
				max_p += p
		return (jobs_done, max_p)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: -1 * x.profit)
		mxl = 10 ** 5
		occupied = [False] * (mxl + 1)
		ans = 0
		count = 0
		for i in range(n):
			jobs = Jobs[i]
			id = jobs.id
			p = jobs.profit
			dd = jobs.deadline
			for time in range(dd - 1, -1, -1):
				if occupied[time]:
					continue
				occupied[time] = True
				ans += p
				count += 1
				break
		return (count, ans)


class Solution:

	def JobScheduling(self, jobs, n):
		ma = 0
		res = []
		for i in range(0, len(jobs)):
			k = [jobs[i].deadline, jobs[i].profit]
			res.append(k)
			if jobs[i].deadline > ma:
				ma = jobs[i].deadline
		res.sort(key=lambda x: x[1], reverse=True)
		a = [0 for z in range(0, ma)]
		p = 0
		c = 0
		for i in range(0, len(res)):
			for j in range(res[i][0] - 1, -1, -1):
				if a[j] == 0:
					a[j] = 1
					p += res[i][1]
					c += 1
					break
		return [c, p]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		(profit, count) = (0, 0)
		res = [False] * 100
		for i in range(n):
			for j in range(Jobs[i].deadline - 1, -1, -1):
				if res[j] == False:
					res[j] = True
					profit += Jobs[i].profit
					count += 1
					break
		return (count, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		(max_profit, n_jobs) = (0, 0)
		Jobs.sort(reverse=True, key=lambda x: x.profit)
		max_deadline = 0
		for i in Jobs:
			if i.deadline > max_deadline:
				max_deadline = i.deadline
		freq_arr = [-1] * (max_deadline + 1)
		for i in Jobs:
			for j in range(i.deadline, 0, -1):
				if freq_arr[j] == -1:
					freq_arr[j] = i.id
					n_jobs += 1
					max_profit += i.profit
					break
		return [n_jobs, max_profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		j = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		max_d = 0
		for jb in Jobs:
			max_d = max(max_d, jb.deadline)
		time = set()
		for i in range(1, max_d + 1):
			time.add(i)
		ans = 0
		k = 0
		for i in range(n):
			if len(time) == 0:
				break
			jb = j[i]
			dd = jb.deadline
			while dd > 0:
				if dd in time:
					k += 1
					ans += jb.profit
					time.remove(dd)
					break
				else:
					dd -= 1
		return (k, ans)


class Solution:

	def JobScheduling(self, jobs, n):
		jobs.sort(key=lambda x: x.profit)
		jobs.reverse()
		maxDeadline = max(map(lambda x: x.deadline, jobs))
		arr = [True for _ in range(maxDeadline)]
		(count, profit) = (0, 0)
		for job in jobs:
			for i in range(job.deadline - 1, -1, -1):
				if arr[i]:
					arr[i] = False
					count += 1
					profit += job.profit
					break
		return [count, profit]


from heapq import heappush, heappop

class Solution:

	def JobScheduling(self, Jobs, n):
		h = []
		ans = [0, 0]
		Jobs.sort(key=lambda x: x.deadline)
		for i in range(n - 1, -1, -1):
			if i == 0:
				slots = Jobs[i].deadline
			else:
				slots = Jobs[i].deadline - Jobs[i - 1].deadline
			heappush(h, (-Jobs[i].profit, Jobs[i].deadline))
			while slots and h:
				temp = heappop(h)
				ans[0] += 1
				ans[1] += -temp[0]
				slots -= 1
		return ans


class Solution:

	def JobScheduling(self, Jobs, n):
		maxi = 0
		arr = []
		for i in range(n):
			maxi = max(maxi, Jobs[i].deadline)
		result = [-1 for i in range(maxi)]
		total = 0
		jobs_done = 0
		for i in range(n):
			arr.append([Jobs[i].profit, Jobs[i].deadline])
		arr.sort(reverse=True)
		for i in range(n):
			for j in range(arr[i][1] - 1, -1, -1):
				if result[j] == -1:
					result[j] = i
					jobs_done += 1
					total += arr[i][0]
					break
		return [jobs_done, total]


class Solution:

	def JobScheduling(self, jobs, n):
		jobs.sort(key=lambda x: x.profit, reverse=True)
		time = 0
		profit = 0
		slots = [0] * n
		for i in jobs:
			for j in range(i.deadline - 1, -1, -1):
				if slots[j] == 0:
					slots[j] = 1
					time += 1
					profit += i.profit
					break
		return (time, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		jobs = sorted(Jobs, key=lambda job: job.profit, reverse=True)
		number = 0
		profit = 0
		time = [None] * n
		for i in jobs:
			for j in range(i.deadline, 0, -1):
				if time[j - 1] == None:
					time[j - 1] = i.profit
					number += 1
					profit += i.profit
					break
		return [number, profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		maxiDeadline = 0
		for i in range(n):
			if Jobs[i].deadline > maxiDeadline:
				maxiDeadline = Jobs[i].deadline
		slot = [-1] * (maxiDeadline + 1)
		countJobs = 0
		maxProfit = 0
		for i in range(n):
			for j in reversed(range(1, Jobs[i].deadline + 1)):
				if slot[j] == -1:
					slot[j] = i
					countJobs += 1
					maxProfit += Jobs[i].profit
					break
		return [countJobs, maxProfit]


from heapq import *

class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.deadline)
		pq = []
		heapify(pq)
		dtime = 0
		ans = 0
		cnt = 0
		for job in Jobs:
			if job.deadline > dtime:
				dtime += 1
				heappush(pq, job.profit)
				ans += job.profit
				cnt += 1
			elif pq and pq[0] < job.profit:
				ans -= heappop(pq)
				heappush(pq, job.profit)
				ans += job.profit
		return (cnt, ans)


class DisjointSet:

	def __init__(self, n):
		self.parent = [i for i in range(n)]

	def find(self, x):
		if x == self.parent[x]:
			return x
		self.parent[x] = self.find(self.parent[x])
		return self.parent[x]

	def merge(self, x, y):
		self.parent[y] = x

class Solution:

	def findMaxDeadline(self, arr):
		ans = 0
		for job in arr:
			if job.deadline > ans:
				ans = job.deadline
		return ans

	def JobScheduling(self, arr, n):
		arr = sorted(arr, key=lambda x: x.profit, reverse=True)
		m = self.findMaxDeadline(arr)
		dsu = DisjointSet(m + 1)
		(count, profit) = (0, 0)
		for job in arr:
			available_slot = dsu.find(job.deadline)
			if available_slot > 0:
				count += 1
				profit += job.profit
				dsu.merge(dsu.find(available_slot - 1), available_slot)
		return (count, profit)


import math
import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.deadline)
		arr = []
		heapq.heapify(arr)
		csz = 1
		for job in Jobs:
			d = job.deadline
			p = job.profit
			csz = max(d, csz)
			if len(arr) < csz:
				heapq.heappush(arr, p)
			elif p > arr[0]:
				heapq.heappushpop(arr, p)
		return [len(arr), sum(arr)]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		m = 0
		for x in Jobs:
			if x.deadline > m:
				m = x.deadline
		r = [-1] * (m + 1)
		a = [0, 0]
		for i in Jobs:
			for j in range(i.deadline, 0, -1):
				if r[j] == -1:
					a[0] += 1
					a[1] += i.profit
					r[j] = 1
					break
		return a


class Solution:

	def JobScheduling(self, jobs, n):
		jobs.sort(key=lambda x: x.profit, reverse=True)
		maxDeadline = max(jobs, key=lambda x: x.deadline).deadline
		sequence = {}
		total_jobs = 0
		total_profit = 0
		for job in jobs:
			index = job.deadline - 1
			while index >= 0 and index in sequence:
				index -= 1
			if index >= 0:
				sequence[index] = job.id
				total_jobs += 1
				total_profit += job.profit
		return (total_jobs, total_profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		jobs = []
		for i in range(n):
			jobs.append([Jobs[i].deadline, Jobs[i].profit])

		def sort(jobs):
			r = sorted(jobs, key=lambda x: x[1], reverse=True)
			return r
		arr = sort(jobs)
		visited = [False] * (len(jobs) + 1)
		pro = 0
		co = 0
		for i in range(n):
			if not visited[arr[i][0]]:
				visited[arr[i][0]] = True
				pro += arr[i][1]
				co += 1
			else:
				for j in range(arr[i][0] - 1, 0, -1):
					if not visited[j]:
						pro += arr[i][1]
						visited[j] = True
						co += 1
						break
		return (co, pro)


class Solution:

	def JobScheduling(self, Jobs, n):
		profits = []
		length = 0
		for i in range(n):
			length = max(length, Jobs[i].deadline)
			profits.append([Jobs[i].deadline, Jobs[i].profit])
		profits.sort(key=lambda x: x[1], reverse=True)
		check = [0] * (length + 1)
		profit = counter = 0
		for j in range(n):
			ind = profits[j][0]
			while ind > 0 and check[ind]:
				ind -= 1
			if ind == 0:
				continue
			check[ind] = 1
			counter += 1
			profit += profits[j][1]
			if counter == length:
				break
		return [counter, profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		maxDead = max((job.deadline for job in Jobs))
		slots = [-1 for i in range(maxDead)]
		maxProf = 0
		count = 0
		for i in range(n):
			for j in range(Jobs[i].deadline - 1, -1, -1):
				if slots[j] == -1:
					slots[j] = Jobs[i].id
					count += 1
					maxProf += Jobs[i].profit
					break
		return (count, maxProf)


import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		profit_and_deadline = []
		max_deadline = 0
		for Job in Jobs:
			max_deadline = max(max_deadline, Job.deadline)
			profit_and_deadline.append([-Job.profit, Job.deadline])
		heapq.heapify(profit_and_deadline)
		slots = [0] * max_deadline
		(total_profit, job_count) = (0, 0)
		while profit_and_deadline:
			(profit, deadline) = heapq.heappop(profit_and_deadline)
			for slot in range(deadline - 1, -1, -1):
				if not slots[slot]:
					total_profit += -1 * profit
					job_count += 1
					slots[slot] = 1
					break
		return [job_count, total_profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		max1 = Jobs[0].deadline
		for i in range(n):
			max1 = max(max1, Jobs[i].deadline)
		arr = [-1] * (max1 + 1)
		countjobs = 0
		maxprofit = 0
		for i in range(n):
			for j in range(Jobs[i].deadline, 0, -1):
				if arr[j] == -1:
					arr[j] = i
					countjobs += 1
					maxprofit += Jobs[i].profit
					break
		return (countjobs, maxprofit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: -x.profit)
		slot = [False] * (n + 1)
		maxprofit = 0
		cnt = 0
		for i in range(n):
			for j in range(Jobs[i].deadline, 0, -1):
				if slot[j] == False:
					maxprofit += Jobs[i].profit
					slot[j] = True
					cnt += 1
					break
		return [cnt, maxprofit]


class Solution:

	def JobScheduling(self, jobs, n):
		jobs.sort(key=lambda x: x.profit, reverse=True)
		slots = [False] * n
		max_profit = 0
		num_jobs = 0
		for i in range(n):
			for j in range(min(n, jobs[i].deadline) - 1, -1, -1):
				if not slots[j]:
					slots[j] = True
					max_profit += jobs[i].profit
					num_jobs += 1
					break
		return (num_jobs, max_profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		maxi = Jobs[0].deadline
		for i in range(1, n):
			maxi = max(maxi, Jobs[i].deadline)
		slot = [-1] * (maxi + 1)
		countjob = 0
		jobprofit = 0
		for i in range(n):
			for j in range(Jobs[i].deadline, 0, -1):
				if slot[j] == -1:
					slot[j] = i
					jobprofit += Jobs[i].profit
					countjob += 1
					break
		return (countjob, jobprofit)


class Solution:

	def JobScheduling(self, jobs, n):
		jobs.sort(key=lambda x: x.profit, reverse=True)
		maxi = jobs[0].deadline
		for i in range(1, len(jobs)):
			maxi = max(maxi, jobs[i].deadline)
		slot = [-1] * (maxi + 1)
		countJobs = 0
		jobProfit = 0
		for i in range(len(jobs)):
			for j in range(jobs[i].deadline, 0, -1):
				if slot[j] == -1:
					slot[j] = i
					countJobs += 1
					jobProfit += jobs[i].profit
					break
		return (countJobs, jobProfit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		maxi = -sys.maxsize
		for i in range(0, n):
			maxi = max(maxi, Jobs[i].deadline)
		schedule = [-1 for i in range(maxi + 1)]
		count = 0
		maxProfit = 0
		for i in range(0, n):
			currProfit = Jobs[i].profit
			currDeadline = Jobs[i].deadline
			currId = Jobs[i].id
			for k in range(currDeadline, 0, -1):
				if schedule[k] == -1:
					count += 1
					maxProfit += currProfit
					schedule[k] = currId
					break
		return [count, maxProfit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: -x.profit)
		maxi = 0
		for i in range(n):
			maxi = max(Jobs[i].profit, maxi)
		slots = [-1] * maxi
		p = 0
		c = 0
		for i in range(n):
			dead = Jobs[i].deadline - 1
			for j in range(dead, -1, -1):
				if slots[j] == -1:
					slots[j] = Jobs[i].id
					p += Jobs[i].profit
					c += 1
					break
		return [c, p]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		no = 0
		profit = 0
		visited = [0] * n
		for i in Jobs:
			for j in range(i.deadline - 1, -1, -1):
				if visited[j] == 0:
					visited[j] = 1
					no += 1
					profit += i.profit
					break
		return (no, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		given = []
		for i in range(n):
			given.append([Jobs[i].deadline, Jobs[i].profit])
		given.sort(key=lambda x: x[1], reverse=True)
		jobsdone = [False] * n
		profit = []
		for i in range(n):
			j = given[i][0]
			for k in range(j - 1, -1, -1):
				if jobsdone[k] is False:
					profit.append(given[i][1])
					jobsdone[k] = True
					break
		return [len(profit), sum(profit)]


class Solution:

	def JobScheduling(self, Jobs, n):
		stateMap = [0 for _ in range(n)]
		sortedJobs = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		profitSum = 0
		jobsDone = 0
		for job in sortedJobs:
			for currState in range(job.deadline - 1, -1, -1):
				if not stateMap[currState]:
					stateMap[currState] = 1
					profitSum += job.profit
					jobsDone += 1
					break
		return (jobsDone, profitSum)


class Solution:

	def JobScheduling(self, Jobs, n):
		(res, count) = (0, 0)
		Jobs = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		result = [0 for i in range(n)]
		slot = [False for i in range(n)]
		for i in range(n):
			for j in range(min(n, Jobs[i].deadline) - 1, -1, -1):
				if not slot[j]:
					result[j] = i
					slot[j] = True
					break
		for i in range(n):
			if slot[i]:
				res += Jobs[result[i]].profit
				count += 1
		ans = []
		ans.append(count)
		ans.append(res)
		return ans


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		max_deadline = -1
		for i in range(n):
			if Jobs[i].deadline > max_deadline:
				max_deadline = Jobs[i].deadline
		arr = [-1] * max_deadline
		count = 0
		profit = 0
		for i in range(n):
			if arr[Jobs[i].deadline - 1] == -1:
				arr[Jobs[i].deadline - 1] = Jobs[i].id
				count += 1
				profit += Jobs[i].profit
			else:
				k = Jobs[i].deadline - 1 - 1
				for x in range(k, -1, -1):
					if arr[x] == -1:
						arr[x] = Jobs[i].id
						count += 1
						profit += Jobs[i].profit
						break
		return [count, profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Job = [[a.id, a.deadline, a.profit] for a in Jobs]
		Job.sort(key=lambda x: x[2], reverse=True)
		slots = [False for i in range(n)]
		tm = 0
		prof = 0
		for i in range(n):
			jb = Job[i]
			for j in range(jb[1] - 1, -1, -1):
				if slots[j] == False:
					slots[j] = True
					prof += jb[2]
					tm += 1
					break
		return (tm, prof)


class Solution:

	def JobScheduling(self, jobs, n):
		lookup = set()
		jobs.sort(key=lambda x: x.profit, reverse=True)
		mdl = jobs[0].deadline
		for jb in jobs:
			mdl = max(mdl, jb.deadline)
		is_worked = [False] * mdl
		count = 0
		profit = 0
		for jb in jobs:
			for j in range(jb.deadline - 1, -1, -1):
				if not is_worked[j]:
					profit += jb.profit
					count += 1
					is_worked[j] = True
					break
		return (count, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		maxDeadline = -1
		for i in Jobs:
			if i.deadline > maxDeadline:
				maxDeadline = i.deadline
		result = [-1 for i in range(maxDeadline + 1)]
		jobcount = 0
		maxprofit = 0
		for i in range(n):
			for j in range(Jobs[i].deadline, 0, -1):
				if result[j] == -1:
					result[j] = i
					jobcount += 1
					maxprofit += Jobs[i].profit
					break
		return [jobcount, maxprofit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(reverse=True, key=lambda x: x.profit)
		vac = [0] * n
		for job in Jobs:
			h = job.deadline - 1
			l = 0
			res = -1
			for i in range(h, -1, -1):
				if not vac[i]:
					res = i
					break
			if res != -1:
				vac[res] = job.profit
		tot = 0
		c = 0
		for ele in vac:
			if ele:
				c += 1
				tot += ele
		return [c, tot]


class Solution:

	def JobScheduling(self, Jobs, n):
		sr = sorted(Jobs, key=lambda job: job.profit, reverse=True)
		co = 0
		pr = 0
		st = set()
		for i in range(n):
			if sr[i].deadline not in st:
				pr += sr[i].profit
				co += 1
				st.add(sr[i].deadline)
			else:
				t = self.findmin(st, sr[i].deadline)
				if t > 0:
					pr += sr[i].profit
					co += 1
					st.add(t)
		return [co, pr]

	def findmin(self, st, dl):
		for i in range(dl, 0, -1):
			if i not in st:
				return i
		return 0


class Solution:

	def JobScheduling(self, Jobs, n):
		job_count = 0
		profit = 0
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		max_time = max(Jobs, key=lambda x: x.deadline).deadline
		profit_list = [0] * max_time
		for job in Jobs:
			if job.deadline <= max_time:
				for j in range(job.deadline - 1, -1, -1):
					if profit_list[j] == 0:
						profit_list[j] = 1
						profit = profit + job.profit
						job_count += 1
						break
		return [job_count, profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: -x.profit)
		max_deadline = Jobs[0].deadline
		for job in Jobs:
			max_deadline = max(max_deadline, job.deadline)
		deadlines = [-1] * (max_deadline + 1)
		max_profit = 0
		cnt = 0
		for job in Jobs:
			for i in range(job.deadline, 0, -1):
				if deadlines[i] == -1:
					deadlines[i] = job.deadline
					max_profit += job.profit
					cnt += 1
					break
		return (cnt, max_profit)


class Solution:

	def JobScheduling(self, jobs, n):
		jobs.sort(key=lambda x: x.profit, reverse=True)
		maxi = jobs[0].deadline
		for i in range(1, len(jobs)):
			maxi = max(maxi, jobs[i].deadline)
		slots = [-1] * (maxi + 1)
		max_profit = 0
		no = 0
		for i in range(n):
			for j in range(jobs[i].deadline, 0, -1):
				if slots[j] == -1:
					slots[j] = i
					no += 1
					max_profit += jobs[i].profit
					break
		return (no, max_profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		max_deadline = 0
		for i in range(n):
			max_deadline = max(Jobs[i].deadline, max_deadline)
		sceduling = [-1 for _ in range(max_deadline + 1)]
		totalProfit = 0
		count = 0
		for i in range(n):
			currProfit = Jobs[i].profit
			currDeadline = Jobs[i].deadline
			currId = Jobs[i].id
			for k in range(currDeadline, 0, -1):
				if sceduling[k] == -1:
					sceduling[k] = currId
					count += 1
					totalProfit += currProfit
					break
		return (count, totalProfit)


class Solution:

	def JobScheduling(self, Jobs, n):
		array = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		visited = [0] * n
		day = 0
		profit = 0
		for i in range(n):
			j = min(n, array[i].deadline - 1)
			for j in range(j, -1, -1):
				if visited[j] == 0:
					visited[j] = 1
					profit += array[i].profit
					day += 1
					break
		return (day, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		max_deadline = 0
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		for i in Jobs:
			max_deadline = max(max_deadline, i.deadline)
		possible_deadlines = [0] * max_deadline
		count = 0
		for i in Jobs:
			if possible_deadlines[i.deadline - 1] == 0:
				possible_deadlines[i.deadline - 1] = i.profit
			else:
				for j in range(i.deadline - 1, -1, -1):
					if possible_deadlines[j] == 0:
						possible_deadlines[j] = i.profit
						break
		x = 0
		for i in possible_deadlines:
			if i != 0:
				x += 1
		return [x, sum(possible_deadlines)]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		places = [False for _ in range(n)]
		res = 0
		count = 0
		for i in range(n):
			for j in reversed(range(min(n - 1, Jobs[i].deadline - 1) + 1)):
				if places[j] == False:
					res += Jobs[i].profit
					places[j] = True
					count += 1
					break
		return (count, res)


class Solution:

	def JobScheduling(self, Jobs, n):
		import heapq
		ans = 0
		profits = []
		Jobs.sort(key=lambda x: x.deadline)
		for i in range(n):
			if len(profits) < Jobs[i].deadline:
				heapq.heappush(profits, Jobs[i].profit)
				ans += Jobs[i].profit
			elif len(profits) == Jobs[i].deadline and profits[0] < Jobs[i].profit:
				pro = heapq.heappop(profits)
				heapq.heappush(profits, Jobs[i].profit)
				ans += Jobs[i].profit - pro
		return [len(profits), ans]


class Solution:

	def JobScheduling(self, Jobs, n):
		arr = [0] * n
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		max_profit = 0
		count = 0
		for i in range(n):
			for j in range(Jobs[i].deadline - 1, -1, -1):
				if not arr[j]:
					arr[j] = True
					max_profit += Jobs[i].profit
					count += 1
					break
		return [count, max_profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		maxjobs = 0
		for job in Jobs:
			if maxjobs < job.deadline:
				maxjobs = job.deadline
		arrans = [-1] * (maxjobs + 1)
		for job in Jobs:
			i = job.deadline
			while i > 0:
				if arrans[i] == -1:
					arrans[i] = job.profit
					break
				i = i - 1
		ans = 0
		c = 0
		for a in arrans:
			if a != -1:
				c = c + 1
				ans = ans + a
		return [c, ans]


import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.deadline)
		result = []
		maxHeap = []
		total = 0
		for i in range(n - 1, -1, -1):
			if i == 0:
				slots_available = Jobs[i].deadline
			else:
				slots_available = Jobs[i].deadline - Jobs[i - 1].deadline
			heapq.heappush(maxHeap, (-Jobs[i].profit, Jobs[i].deadline, Jobs[i].id))
			while slots_available and maxHeap:
				(profit, deadline, jobId) = heapq.heappop(maxHeap)
				slots_available -= 1
				total += profit
				result.append([jobId, deadline, profit])
		count = len(result)
		return [count, -total]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		max_deadline = 0
		for job in Jobs:
			max_deadline = max(max_deadline, job.deadline)
		schedule = [-1] * (max_deadline + 1)
		cnt = 0
		total_profit = 0
		for job in Jobs:
			for k in range(job.deadline, 0, -1):
				if schedule[k] == -1:
					total_profit += job.profit
					cnt += 1
					schedule[k] = job.id
					break
		return (cnt, total_profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		s_jobs = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		maxV = max([job.deadline for job in Jobs])
		arr = [-1] * (maxV + 1)
		sumV = 0
		count = 0
		for i in range(n):
			if arr[s_jobs[i].deadline] == -1:
				sumV += s_jobs[i].profit
				count += 1
				arr[s_jobs[i].deadline] = s_jobs[i].id
			else:
				for j in range(s_jobs[i].deadline - 1, 0, -1):
					if arr[j] == -1:
						arr[j] = s_jobs[i].id
						sumV += s_jobs[i].profit
						count += 1
						break
		return (count, sumV)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		maxi = Jobs[0].deadline
		for i in range(n):
			maxi = max(maxi, Jobs[i].deadline)
		arr = [0 for i in range(maxi)]
		count = 0
		profits = 0
		for i in range(n):
			for j in range(Jobs[i].deadline - 1, -1, -1):
				if arr[j] == 0:
					arr[j] = Jobs[i].id
					count += 1
					profits += Jobs[i].profit
					break
		res = [count, profits]
		return res


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		max_dead = Jobs[0].deadline
		for i in range(n):
			max_dead = max(max_dead, Jobs[i].deadline)
		arr = [0 for i in range(max_dead)]
		(c, profit) = (0, 0)
		for i in range(n):
			for j in range(Jobs[i].deadline - 1, -1, -1):
				if arr[j] == 0:
					arr[j] = Jobs[i].id
					c += 1
					profit += Jobs[i].profit
					break
		return [c, profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		maxi = 0
		for job in Jobs:
			if job.deadline > maxi:
				maxi = job.deadline
		jobs_line = [0 for i in range(maxi + 1)]
		(jobs_count, jobs_sum) = (0, 0)
		for job in Jobs:
			for dead_line in range(job.deadline - 1, -1, -1):
				if jobs_line[dead_line] == 0:
					jobs_line[dead_line] = 1
					jobs_count += 1
					jobs_sum += job.profit
					break
		return [jobs_count, jobs_sum]


from heapq import heapify, heappush, heappop
from collections import defaultdict

class Solution:

	def JobScheduling(self, job, n):
		heap = []
		maxi = 0
		sumi = 0
		count = 0
		for i in job:
			(a, b, c) = (i.deadline, i.id, i.profit)
			heappush(heap, [-c, a])
			maxi = max(maxi, a)
		arr = [-1] * maxi
		d = defaultdict(int)
		while heap:
			(a, b) = heappop(heap)
			if d[b - 1] < b and count < maxi:
				for i in range(b - 1, -1, -1):
					if arr[i] == -1:
						arr[i] = -a
						sumi += -a
						count += 1
						d[b - 1] += 1
						break
		return [count, sumi]


import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		minheap = []
		heapq.heapify(minheap)
		T = 0
		sorted_jobs = sorted(Jobs, key=lambda x: x.deadline)
		for job in sorted_jobs:
			deadline = job.deadline
			profit = job.profit
			if deadline > T:
				heapq.heappush(minheap, profit)
				T += 1
			elif profit > minheap[0]:
				heapq.heappop(minheap)
				heapq.heappush(minheap, profit)
		sumProfit = 0
		size = len(minheap)
		for _ in range(len(minheap)):
			sumProfit += heapq.heappop(minheap)
		return [size, sumProfit]


def func(x):
	return x.deadline
import sys
sys.setrecursionlimit(10 ** 6)

class Solution:

	def helper(self, A, i, c):
		key = (i, c)
		if self.d.get(key) is not None:
			return self.d[key]
		if i == len(A):
			return (0, 0)
		if c < A[i].deadline:
			(n1, c1) = self.helper(A, i + 1, c + 1)
			(n2, c2) = self.helper(A, i + 1, c)
			if A[i].profit + c1 > c2:
				self.d[key] = (n1 + 1, A[i].profit + c1)
			else:
				self.d[key] = (n2, c2)
		else:
			self.d[key] = self.helper(A, i + 1, c)
		return self.d[key]

	def JobScheduling(self, A, n):
		visited = set()
		A.sort(key=lambda x: x.profit)
		profit = 0
		for i in range(n - 1, -1, -1):
			time = A[i].deadline
			while time > 0 and time in visited:
				time -= 1
			if time > 0:
				profit += A[i].profit
				visited.add(time)
		return (len(visited), profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		time = [0] * max(Jobs, key=lambda x: x.deadline).deadline
		for job in Jobs:
			if time[job.deadline - 1] == 0:
				time[job.deadline - 1] = (job.id, job.profit)
			else:
				for i in reversed(range(job.deadline)):
					if time[i] == 0:
						time[i] = (job.id, job.profit)
						break
		max_profit = sum((i[1] for i in time if isinstance(i, tuple)))
		total_num = sum((1 for i in time if isinstance(i, tuple)))
		return [total_num, max_profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		l = Jobs
		l.sort(reverse=True, key=lambda x: x.profit)
		max = 0
		for i in l:
			if i.deadline > max:
				max = i.deadline
		l1 = [0] * max
		c = 0
		for i in l:
			j = i.deadline - 1
			while True:
				if l1[j] == 0:
					l1[j] = i.profit
					c = c + 1
					break
				else:
					j -= 1
					if j < 0:
						break
			if c == max:
				break
		c1 = 0
		sum = 0
		for i in l1:
			if i != 0:
				sum += i
				c1 += 1
		return [c1, sum]


class Solution:

	def JobScheduling(self, Jobs, n):
		jobday = [-1] * max(Jobs, key=lambda x: x.deadline).deadline
		profit = 0
		count = 0
		Jobs.sort(key=lambda x: [-x.profit])
		for x in Jobs:
			(id, dl, pr) = (x.id, x.deadline, x.profit)
			j = dl - 1
			while 0 <= j and jobday[j] != -1:
				j -= 1
			if j == -1:
				continue
			jobday[j] = id
			profit += pr
			count += 1
			if count == len(jobday):
				break
		return (count, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.deadline)
		from heapq import heapify, heappop, heappush

		def set_job(job):
			(d, p) = (job.deadline, job.profit)
			return (-p, d)
		q = []
		heapify(q)
		i = n - 1
		(profit, count) = (0, 0)
		while i >= 0:
			deadline = Jobs[i].deadline
			while i >= 0 and Jobs[i].deadline == deadline:
				job = set_job(Jobs[i])
				heappush(q, job)
				i -= 1
			slots = deadline
			if i >= 0:
				slots -= Jobs[i].deadline
			while slots > 0 and q:
				slots -= 1
				job = heappop(q)
				profit += -job[0]
				count += 1
		return (count, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		(day, profit) = (0, 0)
		res = [0] * n
		for i in range(n):
			j = min(n, Jobs[i].deadline - 1)
			for j in range(j, -1, -1):
				if res[j] == 0:
					res[j] = 1
					profit += Jobs[i].profit
					day += 1
					break
		return (day, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		done = [-1] * 101
		cost = 0
		ans = 0
		count = 0
		for i in range(n):
			cost = Jobs[i].profit
			serial = Jobs[i].id
			dead = Jobs[i].deadline
			for j in range(dead, 0, -1):
				if done[j] == -1:
					done[j] = serial
					ans += cost
					count += 1
					break
		return (count, ans)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		vis = [-1] * n
		ans = 0
		cnt = 0
		for i in range(n):
			job = Jobs[i]
			if vis[job.deadline - 1] == -1:
				vis[job.deadline - 1] = job.id
				ans += job.profit
				cnt += 1
			else:
				for curr in range(job.deadline - 2, -1, -1):
					if vis[curr] == -1:
						vis[curr] = job.id
						ans += job.profit
						cnt += 1
						break
		return [cnt, ans]


from collections import defaultdict

class Solution:

	def JobScheduling(self, jobs, n):
		m = defaultdict(list)
		for i in jobs:
			m[i.deadline].append(i.profit)
		ans = []
		for i in sorted(m.keys()):
			for j in m[i]:
				ans.append(j)
				if len(ans) > i:
					ans.remove(min(ans))
		return [len(ans), sum(ans)]


class Solution:

	def JobScheduling(self, Jobs, n):

		def sortProfit(x):
			return x.profit
		profit = 0
		numberOfJobs = 0
		slot = [-1] * (n + 1)
		slot[0] = 1
		arr = list(Jobs)

		def checkSlot(d):
			for i in range(d, -1, -1):
				if slot[i] == -1:
					return i
			return -1
		arr.sort(key=sortProfit, reverse=True)
		for i in range(n):
			s = checkSlot(arr[i].deadline)
			if s > -1:
				slot[s] = 1
				numberOfJobs += 1
				profit += arr[i].profit
		return [numberOfJobs, profit]


class Solution:

	def JobScheduling(self, jobs, n):
		jobs.sort(key=lambda x: x.profit, reverse=True)
		(profit, totalJ) = (0, 0)
		visited = [-1] * (n + 1)
		for i in range(n):
			for j in range(jobs[i].deadline, 0, -1):
				if visited[j] == -1:
					profit += jobs[i].profit
					totalJ += 1
					visited[j] = jobs[i].id
					break
		return (totalJ, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		max_deadline = max([job.deadline for job in Jobs])
		slots = [False] * (max_deadline + 1)
		sum1 = 0
		c = 0
		for job in Jobs:
			for j in range(job.deadline, 0, -1):
				if not slots[j]:
					slots[j] = True
					sum1 += job.profit
					c += 1
					break
		return (c, sum1)


import heapq

class Solution:

	def JobScheduling(self, jobs, n):
		profit = 0
		count = 0
		jobs.sort(key=lambda x: x.deadline)
		heap = []
		for i in range(n - 1, -1, -1):
			heapq.heappush(heap, -jobs[i].profit)
			if i == 0:
				slots = jobs[0].deadline
			else:
				slots = jobs[i].deadline - jobs[i - 1].deadline
			while slots > 0 and len(heap):
				profit += -heapq.heappop(heap)
				count += 1
				slots -= 1
		return (count, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		dead = -1
		for i in range(n):
			if Jobs[i].deadline > dead:
				dead = Jobs[i].deadline
		ans = [-1] * dead
		maxp = 0
		count = 0
		for i in range(0, n):
			d = Jobs[i].deadline
			for j in range(d - 1, -1, -1):
				if ans[j] == -1:
					ans[j] = Jobs[i].id
					count = count + 1
					maxp = maxp + Jobs[i].profit
					break
		l = [count, maxp]
		return l


class Solution:

	def JobScheduling(self, Jobs, n):
		if not Jobs or Jobs == None or Jobs == {}:
			return []
		maxi = 0
		for i in Jobs:
			maxi = max(maxi, i.deadline)
		out = 0
		cj = 0
		Jobs = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		seq = [-1] * (maxi + 1)
		for i in Jobs:
			k = i.deadline - 1
			while seq[k] != -1:
				k -= 1
			if k >= 0:
				seq[k] = i.id
				cj += 1
				out += i.profit
		return [cj, out]


from collections import defaultdict
import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		jobs = [(job.deadline, job.profit, job.id) for job in Jobs]
		jobs.sort()
		job_dict = defaultdict(list)
		for (deadline, profit, id) in jobs:
			job_dict[deadline].append((profit, id))
		max_profit = 0
		heap = []
		for deadline in range(n, 0, -1):
			if deadline in job_dict:
				for (profit, job_id) in job_dict[deadline]:
					heapq.heappush(heap, (-profit, job_id))
			if heap:
				max_profit -= heapq.heappop(heap)[0]
		jobs_done = len(jobs) - len(heap)
		return [jobs_done, max_profit]