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 if and only if the job is completed by its deadline. The task is to 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:
Since at deadline 1 Job3 can give the maximum profit and for deadline 4 we left with only Job1 hence 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 an array ans[ ] in which ans[0] contains the count of jobs and ans[1] contains maximum profit.
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 Job:

#     '''

#     Job class which stores profit and deadline.

#     '''

#     def __init__(self,profit=0,deadline=0):

#         self.profit = profit

#         self.deadline = deadline

#         self.id = 0



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):
		temp = [0] * n

		def fn(ele):
			return ele.profit
		Jobs.sort(key=fn, reverse=True)
		for i in range(n):
			if temp[Jobs[i].deadline - 1] == 0:
				temp[Jobs[i].deadline - 1] = Jobs[i].profit
			elif Jobs[i].profit > temp[Jobs[i].deadline - 1]:
				temp[Jobs[i].deadline - 1] = Jobs[i].profit
			else:
				for j in range(Jobs[i].deadline - 1, -1, -1):
					if Jobs[i].profit > temp[j]:
						temp[j] = Jobs[i].profit
						break
		count = 0
		ans = 0
		for i in range(len(temp)):
			if temp[i] != 0:
				count += 1
				ans += temp[i]
		return [count, ans]


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(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


from heapq import *

class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def JobScheduling(self, Jobs, n):
		ans = [0] * 100
		Jobs = sorted(Jobs, key=lambda x: x.profit, reverse=True)
		profit1 = 0
		profit2 = 0
		slots = [0 for i in range(n)]
		for i in range(n):
			for j in range(Jobs[i].deadline - 1, -1, -1):
				if slots[j] == 0:
					slots[j] = 1
					profit1 += Jobs[i].profit
					profit2 += 1
					break
		return [profit2, profit1]


class KeyWrapper:

	def __init__(self, iterable):
		self.it = iterable

	def __getitem__(self, i):
		return -self.it[i].profit

	def __len__(self):
		return len(self.it)

class Solution:

	def JobScheduling(self, Jobs, n):
		import operator
		from bisect import bisect

		def mixed_order(obj):
			return (obj.deadline, -obj.profit)
		sorted_jobs = sorted(Jobs, key=mixed_order)
		n_jobs = 0
		total_profit = 0
		schedule = []
		current_index = 0
		while current_index < len(sorted_jobs):
			current_job = sorted_jobs[current_index]
			deadline_index = bisect(KeyWrapper(schedule), -current_job.profit)
			schedule = schedule[:deadline_index] + [current_job] + schedule[deadline_index:]
			deadline = current_job.deadline
			n_jobs += 1
			total_profit += current_job.profit
			current_index += 1
			while current_index < len(sorted_jobs) and sorted_jobs[current_index].deadline == deadline and (len(schedule) < deadline):
				deadline_index = bisect(KeyWrapper(schedule[deadline_index + 1:]), -sorted_jobs[current_index].profit) + deadline_index + 1
				schedule = schedule[:deadline_index] + [sorted_jobs[current_index]] + schedule[deadline_index:]
				n_jobs += 1
				total_profit += sorted_jobs[current_index].profit
				current_index += 1
			if current_index >= len(sorted_jobs):
				return [n_jobs, total_profit]
			if sorted_jobs[current_index].deadline == deadline:
				sort_index = bisect(KeyWrapper(schedule[deadline_index + 1:]), -sorted_jobs[current_index].profit) + deadline_index + 1
				while sort_index < len(schedule):
					total_profit += sorted_jobs[current_index].profit - schedule[-1].profit
					schedule = schedule[:sort_index] + [sorted_jobs[current_index]] + schedule[sort_index:-1]
					current_index += 1
					deadline_index = sort_index
					if current_index < len(sorted_jobs) and sorted_jobs[current_index].deadline == deadline:
						sort_index = bisect(KeyWrapper(schedule[deadline_index + 1:]), -sorted_jobs[current_index].profit) + deadline_index + 1
					else:
						break
			while current_index < len(sorted_jobs) and sorted_jobs[current_index].deadline == deadline:
				current_index += 1
		return [n_jobs, total_profit]


class Solution:

	def JobScheduling(self, Jobs, n):

		def tt(Jobs):
			return Jobs.profit
		Jobs = sorted(Jobs, key=tt, reverse=True)
		l = [0] * n
		for i in range(n):
			x = Jobs[i].deadline
			y = Jobs[i].profit
			for i in range(x - 1, -1, -1):
				if l[i] == 0 or l[i] < y:
					l[i] = y
					break
		count = 0
		maxprofit = 0
		for i in range(len(l)):
			if l[i] != 0:
				count += 1
				maxprofit += l[i]
		return [count, maxprofit]


class Solution:

	def JobScheduling(self, jobs, n):
		jobs.sort(key=lambda x: (-x.profit, x.deadline))
		d = 0
		for j in jobs:
			d = max(d, j.deadline)
		res = 0
		slot = [False] * d
		for j in jobs:
			(d, p) = (j.deadline - 1, j.profit)
			for i in range(d, -1, -1):
				if not slot[i]:
					res += p
					slot[i] = True
					break
		return [sum(slot), res]


import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		arr = []
		heap = []
		for i in Jobs:
			arr.append((i.deadline, i.profit))
		arr.sort()
		i = 0
		while i < len(arr):
			heapq.heappush(heap, arr[i][1])
			while len(heap) > arr[i][0]:
				heapq.heappop(heap)
			i += 1
		return [len(heap), sum(heap)]
		return (0, 0)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: (-x.profit, x.deadline))
		(maxx, count, ans) = (0, 0, 0)
		for i in Jobs:
			maxx = max(maxx, i.deadline)
		check = [False] * maxx
		for i in Jobs:
			d = i.deadline
			d -= 1
			for j in range(d, -1, -1):
				if check[j] != True:
					check[j] = True
					ans += i.profit
					count += 1
					break
		return [count, ans]


class Solution:

	def JobScheduling(self, Jobs, n):
		p = 0
		t = 0
		a = [0] * 1000
		Jobs = sorted(Jobs, reverse=True, key=lambda v: v.profit)
		for i in Jobs:
			d = i.deadline
			pr = i.profit
			while d >= 1 and a[d] == 1:
				d -= 1
			if d >= 1:
				a[d] = 1
				t += 1
				p += pr
		return [t, p]


class Solution:

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


class Solution:

	def JobScheduling(self, Jobs, n):
		profit = 0
		count = 0
		l = []
		for i in range(n):
			l.append([Jobs[i].profit, Jobs[i].deadline])
		l.sort(reverse=True)
		time = [0] * n
		for i in range(n):
			for j in range(min(n - 1, l[i][1] - 1), -1, -1):
				if time[j] == 0:
					time[j] = 1
					profit += l[i][0]
					count += 1
					break
		return [count, profit]


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: -x.profit)
		vis = [False] * 101
		(cnt, profit) = (0, 0)
		for i in range(n):
			job = Jobs[i]
			(p, d) = (job.profit, job.deadline)
			if not vis[d]:
				vis[d] = True
				cnt += 1
				profit += p
			else:
				for j in range(d - 1, 0, -1):
					if not vis[j]:
						vis[j] = True
						cnt += 1
						profit += p
						break
		return [cnt, profit]


class Solution:

	def JobScheduling(self, jobs, n):
		sorted_jobs = sorted(jobs, key=lambda x: x.profit, reverse=True)
		res = [False] * n
		job_order = ['-1'] * n
		count = 0
		profit = 0
		for job in sorted_jobs:
			for i in range(min(n, job.deadline) - 1, -1, -1):
				if res[i] is False:
					res[i] = True
					job_order[i] = job.id
					count += 1
					profit += job.profit
					break
		return (count, profit)


import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		jobDict = dict()
		for job in Jobs:
			jobDuration = job.deadline
			jobProfit = job.profit
			if jobDuration not in jobDict:
				jobDict[jobDuration] = []
			if len(jobDict[jobDuration]) < jobDuration:
				heapq.heappush(jobDict[jobDuration], jobProfit)
			elif heapq.nsmallest(1, jobDict[jobDuration])[0] < jobProfit:
				heapq.heappushpop(jobDict[jobDuration], jobProfit)
		acceptedJobProfit = []
		for (duration, jobProfitList) in sorted(jobDict.items()):
			for jobProfit in jobProfitList:
				if len(acceptedJobProfit) < duration:
					heapq.heappush(acceptedJobProfit, jobProfit)
				elif heapq.nsmallest(1, acceptedJobProfit)[0] < jobProfit:
					heapq.heappushpop(acceptedJobProfit, jobProfit)
		totalProfit = 0
		totalProfit = sum(heapq.nsmallest(len(acceptedJobProfit), acceptedJobProfit))
		numberJobs = len(acceptedJobProfit)
		return (numberJobs, totalProfit)


class Solution:

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


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		maxTime = max(Jobs, key=lambda x: x.deadline)
		indexList = [x for x in range(maxTime.deadline - 1, 0, -1)]
		summ = maxTime.profit
		count = 1
		Jobs.remove(maxTime)
		for job in Jobs:
			for i in range(len(indexList)):
				dline = indexList[i]
				if dline <= job.deadline:
					summ += job.profit
					count += 1
					indexList.pop(i)
					break
			if not indexList:
				return (count, summ)
		return (count, summ)


class Solution:

	def JobScheduling(self, Jobs, n):
		d = dict()
		profit = 0
		j_done = 0
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		for j in Jobs:
			if d.get(j.deadline, 1):
				profit += j.profit
				j_done += 1
				d[j.deadline] = 0
			else:
				ind = j.deadline - 1
				while ind > 0:
					if d.get(ind, 1):
						profit += j.profit
						j_done += 1
						d[ind] = 0
						break
					ind -= 1
		return (j_done, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		joblist = []
		check = [False] * n
		for i in Jobs:
			joblist.append([i.profit, i.deadline])
		joblist.sort(reverse=True)
		for i in range(n):
			j = joblist[i][1] - 1
			while j >= 0:
				if check[j] == False:
					check[j] = joblist[i][0]
					break
				j -= 1
		profit1 = 0
		count = 0
		for i in check:
			if i != False:
				profit1 += i
				count += 1
		return [count, profit1]


class Solution:

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


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs = list(Jobs)
		A = [0] * n
		Jobs = sorted(Jobs, key=lambda t: t.profit, reverse=True)
		c = 0
		for i in range(n):
			if A[Jobs[i].deadline - 1] == 0:
				A[Jobs[i].deadline - 1] = Jobs[i].profit
				c += 1
			else:
				j = Jobs[i].deadline - 1
				while A[j] != 0 and j > -1:
					j -= 1
				if j != -1:
					A[j] = Jobs[i].profit
					c += 1
		return (c, sum(A))


class Solution:

	def JobScheduling(self, Jobs, n):

		def get_profit(job):
			return job.profit
		Jobs = sorted(Jobs, key=get_profit, reverse=True)
		slots = [1] * n
		jobs = 0
		profit = 0
		for job in Jobs:
			i = min(job.deadline, n)
			for i in range(job.deadline - 1, -1, -1):
				if slots[i]:
					slots[i] = 0
					jobs += 1
					profit += job.profit
					break
		return (jobs, profit)


class Solution:

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


class Solution:

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


class Solution:

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


class Solution:

	def JobScheduling(self, Jobs, n):
		jobs = []
		maxDeadline = -1
		for i in Jobs:
			curr = [i.deadline, i.profit]
			jobs.append(curr)
			maxDeadline = max(maxDeadline, i.deadline)
		jobs = sorted(jobs, key=lambda x: (-x[1], -x[0]))
		jobsDone = [-1 for i in range(maxDeadline + 1)]
		jobsCompleted = 0
		totalProfit = 0
		for i in range(len(jobs)):
			(deadline, profit) = (jobs[i][0], jobs[i][1])
			if jobsDone[deadline - 1] == -1:
				jobsDone[deadline - 1] = profit
				totalProfit += profit
				jobsCompleted += 1
			else:
				while deadline > 1:
					deadline -= 1
					if jobsDone[deadline - 1] == -1:
						jobsDone[deadline - 1] = profit
						totalProfit += profit
						jobsCompleted += 1
						break
		return [jobsCompleted, totalProfit]


class Solution:

	def JobScheduling(self, Jobs, n):
		maxDline = 0
		l = len(Jobs)
		for i in range(l):
			maxDline = max(maxDline, Jobs[i].deadline)
		boundTime = [0 for i in range(maxDline + 1)]
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		cnt = 0
		maxprofit = 0
		for job in Jobs:
			i = job.deadline
			while i > 0 and boundTime[i] != 0:
				i -= 1
			if i <= 0:
				continue
			boundTime[i] = job.id
			cnt += 1
			maxprofit += job.profit
		return [cnt, maxprofit]


class Solution:

	def JobScheduling(self, Jobs, n):
		sorted_job_list = sorted(Jobs, key=lambda k: -k.profit)
		profit = 0
		jobs_done = 0
		job_seq = [0 for i in range(n)]
		for job in sorted_job_list:
			deadline = job.deadline - 1
			for i in range(deadline, -1, -1):
				if job_seq[i] == 0:
					job_seq[i] = 1
					jobs_done += 1
					profit += job.profit
					break
		return (jobs_done, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		count = 0
		temp = []
		nsum = 0
		arr = [False for _ in range(n)]
		for i in range(0, n):
			t = Jobs[i].deadline - 1
			p = Jobs[i].profit
			while t >= 0:
				if arr[t] is False:
					nsum += p
					count += 1
					arr[t] = True
					t = -1
				else:
					t -= 1
		return (count, nsum)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		job_done = [False] * n
		total_profit = 0
		jobs_done = 0
		for job in Jobs:
			deadline = job.deadline
			while deadline > 0:
				if not job_done[deadline - 1]:
					total_profit += job.profit
					jobs_done += 1
					job_done[deadline - 1] = True
					break
				deadline -= 1
		return (jobs_done, total_profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda j: j.profit, reverse=True)
		scheduled_jobs = {}
		for job in Jobs:
			deadline = job.deadline
			for i in range(deadline, 0, -1):
				if not i in scheduled_jobs:
					scheduled_jobs[i] = job
					break
		scheduled_jobs_list = list(scheduled_jobs.values())
		num_scheduled_jobs = 0
		profit = 0
		for job in scheduled_jobs_list:
			num_scheduled_jobs += 1
			profit += job.profit
		return [num_scheduled_jobs, profit]


import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		arr = []
		for job in Jobs:
			arr.append([job.deadline, job.profit])
		arr.sort(key=lambda x: x[0])
		maxProfit = 0
		heap = []
		for i in range(n):
			if arr[i][0] > len(heap):
				heapq.heappush(heap, arr[i][1])
				maxProfit += arr[i][1]
			else:
				temp = heapq.heappop(heap)
				if temp < arr[i][1]:
					heapq.heappush(heap, arr[i][1])
					maxProfit += arr[i][1]
					maxProfit -= temp
				else:
					heapq.heappush(heap, temp)
		return [len(heap), maxProfit]


import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		arr = []
		maxDeadline = 0
		for i in Jobs:
			arr.append([i.id, i.deadline, i.profit])
			if i.deadline > maxDeadline:
				maxDeadline = i.deadline
		arr.sort(key=lambda x: x[2], reverse=True)
		mark = [-1] * (maxDeadline + 1)
		cnt = 0
		tprofit = 0
		for (id, dead, profit) in arr:
			x = dead
			while x > 0:
				if mark[x] == -1:
					mark[x] = id
					tprofit += profit
					cnt += 1
					break
				else:
					x -= 1
		return [cnt, tprofit]


import heapq

class Solution:

	def JobScheduling(self, Jobs, n):
		res = []
		for i in Jobs:
			res.append([i.deadline, i.profit])
		res.sort()
		h = []
		for i in range(len(res)):
			if len(h) < res[i][0]:
				heapq.heappush(h, res[i][1])
			elif res[i][1] > h[0]:
				heapq.heappop(h)
				heapq.heappush(h, res[i][1])
		k = len(h)
		s = 0
		while len(h) != 0:
			s = s + heapq.heappop(h)
		return [k, s]


class Solution:

	def JobScheduling(self, jobs, n):
		nj = 0
		mpft = 0
		jobs.sort(key=lambda x: -x.profit)
		jobs_done = set()
		min_dl = 0
		for j in jobs:
			(dl, p) = (j.deadline, j.profit)
			while dl > min_dl:
				if dl not in jobs_done:
					jobs_done.add(dl)
					nj += 1
					mpft += p
					break
				dl -= 1
		return (nj, mpft)


from heapq import *

class Solution:

	def JobScheduling(self, Jobs, n):
		arr = []
		for e in Jobs:
			arr.append((e.deadline, e.profit))
		arr.sort(key=lambda x: (x[0], -x[1]))
		count = 0
		profit = 0
		t = 0
		hp = []
		for (d, p) in arr:
			if d <= t:
				if p > hp[0]:
					profit += p - hp[0]
					heappop(hp)
					heappush(hp, p)
			else:
				profit += p
				heappush(hp, p)
				count += 1
				t += 1
		return (count, profit)


class Solution:

	def JobScheduling(self, Jobs, n):
		Jobs.sort(key=lambda x: x.profit, reverse=True)
		max_d = max((job.deadline for job in Jobs))
		slots = (n + 1) * [0]
		(res, days) = (0, 0)
		for i in range(n):
			dl = Jobs[i].deadline
			while dl >= 1:
				if slots[dl] == 0:
					gain = Jobs[i].profit
					res += gain
					days += 1
					slots[dl] = 1
					break
				dl -= 1
		return [days, res]


class Solution:

	def JobScheduling(self, jobs, n):
		jobs.sort(key=lambda x: x.profit, reverse=True)
		d = max(jobs, key=lambda x: x.deadline)
		ans = [0, 0]
		visited = [0] * (d.deadline + 1)
		for i in range(len(jobs)):
			j = jobs[i].deadline
			while j > 0:
				if visited[j] == 1:
					j -= 1
				else:
					ans[1] += jobs[i].profit
					visited[j] = 1
					ans[0] += 1
					break
		return ans


class Solution:

	def JobScheduling(self, Jobs, n):

		def profit(job):
			return job.profit
		count = 0
		pro = 0
		dead = [0] * 100
		Jobs.sort(key=profit, reverse=True)
		for i in Jobs:
			j = i.deadline - 1
			while j >= 0:
				if not dead[j]:
					dead[j] = 1
					count += 1
					pro += i.profit
					break
				j -= 1
		return [count, pro]