Given N activities with their start and finish day given in array start[ ] and end[ ]. Select the maximum number of activities that can be performed by a single person, assuming that a person can only work on a single activity at a given day.
Note : Duration of the activity includes both starting and ending day.
Example 1:
Input:
N = 2
start[] = {2, 1}
end[] = {2, 2}
Output: 
1
Explanation:
A person can perform only one of the
given activities.
Example 2:
Input:
N = 4
start[] = {1, 3, 2, 5}
end[] = {2, 4, 3, 6}
Output: 
3
Explanation:
A person can perform activities 1, 2
and 4.
Your Task :
You don't need to read input or print anything. Your task is to complete the function activityselection() which takes array start[ ], array end[ ] and integer N as input parameters and returns the maximum number of activities that can be done.
Expected Time Complexity : O(N * Log(N))
Expected Auxilliary Space : O(N)
Constraints:
1 ≤ N ≤ 2*10^{5}
1 ≤ start[i] ≤ end[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    

    #Function to find the maximum number of activities that can

    #be performed by a single person.

    def activitySelection(self,n,start,end):

        

        # code here

Solutions:
class Solution:

	def activitySelection(self, n, start, end):
		activity = []
		for i in range(n):
			activity.append([start[i], end[i]])

		def sort_func(ele):
			return ele[1]
		activity.sort(key=sort_func)
		last_activity_end = activity[0][1]
		count = 1
		for i in range(1, n):
			if activity[i][0] > last_activity_end:
				last_activity_end = activity[i][1]
				count += 1
		return count


class Solution:

	def activitySelection(self, n, start, end):
		activity = []
		for i in range(n):
			activity.append([start[i], end[i]])
		activity = sorted(activity, key=lambda x: (x[1], x[0]))
		ans = [activity[0]]
		for i in range(1, len(activity)):
			if activity[i][0] > ans[-1][1]:
				ans.append(activity[i])
		return len(ans)


class Solution:

	def activitySelection(self, n, start, end):
		arr = []
		for i in range(n):
			k = [start[i], end[i]]
			arr.append(k)
		arr.sort(key=lambda x: x[1])
		c = 1
		et = arr[0][1]
		for z in range(1, len(arr)):
			if arr[z][0] > et:
				c += 1
				et = arr[z][1]
		return c


class Solution:

	def activitySelection(self, n, start, end):
		dates = [[start[i], end[i]] for i in range(n)]
		dates.sort(key=lambda x: x[1])
		count = 1
		pre = dates[0][1]
		for i in range(1, n):
			if dates[i][0] > pre:
				count += 1
				pre = dates[i][1]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		meet = []
		for i in range(n):
			meet.append((start[i], end[i]))
		meet.sort(key=lambda x: x[1])
		count = 1
		ansEnd = meet[0][1]
		for i in range(1, n):
			if meet[i][0] > ansEnd:
				count += 1
				ansEnd = meet[i][1]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		aux = [[0 for _ in range(3)] for _ in range(n)]
		for i in range(n):
			aux[i][0] = i + 1
			aux[i][1] = start[i]
			aux[i][2] = end[i]
		aux.sort(key=lambda x: x[2])
		result = [aux[0]]
		prev = aux[0]
		for i in range(1, n):
			if aux[i][1] > prev[2]:
				result.append(aux[i])
				prev = aux[i]
		return len(result)


class Solution:

	def activitySelection(self, n, start, end):
		activity = [(start[i], end[i]) for i in range(n)]
		activity.sort(key=lambda x: x[1])
		count = 1
		finish = activity[0][1]
		for i in range(n):
			if activity[i][0] > finish:
				count += 1
				finish = activity[i][1]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		l = []
		for i in range(n):
			l += [[start[i], end[i]]]
		l = sorted(l, key=lambda l: l[1])
		ans = 1
		i = 0
		for j in range(1, n):
			if l[i][1] < l[j][0]:
				ans += 1
				i = j
		return ans


class Solution:

	def activitySelection(self, n, start, end):
		(count, end_idx) = (1, 0)
		sort = sorted(list(zip(start, end)), key=lambda x: x[1])
		for i in range(1, n):
			if sort[i][0] > sort[end_idx][1]:
				count += 1
				end_idx = i
		return count


class Solution:

	def activitySelection(self, n, start, end):
		count = 1
		arr = []
		for i in range(n):
			arr.append((start[i], end[i]))
		arr = sorted(arr, key=lambda x: x[1])
		l = arr[0][1]
		for i in range(n):
			if l < arr[i][0]:
				count += 1
				l = arr[i][1]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		arr = []
		for i in range(n):
			k = [start[i], end[i]]
			arr.append(k)
		arr.sort(key=lambda x: x[1])
		i = 0
		ans = 1
		for j in range(1, n):
			if arr[j][0] > arr[i][1]:
				ans += 1
				i = j
		return ans


class Solution:

	def activitySelection(self, n, start, end):
		l = []
		for i in range(n):
			l.append([start[i], end[i]])
		l.sort(key=lambda x: x[1])
		count = 1
		i = 0
		j = 1
		while j < n:
			if l[i][1] < l[j][0]:
				i = j
				count += 1
			j += 1
		return count


class Solution:

	def activitySelection(self, n, start, end):
		activity_arr = []
		for i in range(n):
			activity_arr.append([start[i], end[i]])
		activity_arr.sort(key=lambda item: item[1])
		activity_number = 1
		i = 0
		for j in range(1, n):
			if activity_arr[j][0] > activity_arr[i][1]:
				activity_number += 1
				i = j
		return activity_number


class Solution:

	def activitySelection(self, n, start, end):
		x = []
		for i in range(n):
			x.append([[start[i], end[i]], i + 1])
		x.sort(key=lambda t: (t[0][1], t[0][0]))
		last = 0
		res = 0
		for i in range(n):
			if x[i][0][0] > last:
				res += 1
				last = x[i][0][1]
		return res


class Solution:
	from heapq import heappop, heappush

	def activitySelection(self, n, start, end):
		x = []
		for i in range(n):
			x.append([[start[i], end[i]], i + 1])
		x.sort(key=lambda t: (t[0][1], t[0][0]))
		last = 0
		res = 0
		for i in range(n):
			if x[i][0][0] > last:
				res += 1
				last = x[i][0][1]
		return res


class Solution:

	def activitySelection(self, n, start, end):
		p = []
		for i in range(n):
			p.append([start[i], end[i]])
		p.sort(key=lambda x: x[1])
		ct = 1
		end = p[0][1]
		for j in range(1, n):
			if p[j][0] > end:
				ct += 1
				end = p[j][1]
		return ct


from queue import PriorityQueue as pq

class Solution:

	def activitySelection(self, n, start, end):
		arr = []
		for i in range(n):
			k = [start[i], end[i]]
			arr.append(k)
		arr.sort(key=lambda x: x[1])
		i = 0
		ans = 1
		for j in range(1, n):
			if arr[j][0] > arr[i][1]:
				ans += 1
				i = j
		return ans


class Solution:

	def activitySelection(self, n, start, end):
		arr = []
		for i in range(n):
			arr.append([start[i], end[i]])
		arr.sort(key=lambda x: x[1])
		count = 1
		c = 0
		for i in range(1, n):
			if arr[i][0] > arr[c][1]:
				count += 1
				c = i
		return count


class Solution:

	def activitySelection(self, n, start, end):
		act = zip(start, end)
		act_sor = sorted(act, key=lambda task: task[1])
		co = 1
		l = len(act_sor)
		ls = act_sor[0][1]
		for i in range(1, l):
			if act_sor[i][0] > ls:
				co += 1
				ls = act_sor[i][1]
		return co


class Solution:

	def activitySelection(self, n, start, end):
		s = []
		for x in range(n):
			s.append([end[x], start[x]])
		s.sort()
		i = 0
		j = 1
		count = 1
		while i < n and j < n:
			if s[i][0] < s[j][1]:
				count += 1
				i = j
				j += 1
			else:
				j += 1
		return count


class Solution:

	def activitySelection(self, n, start, end):
		arr = []
		for i in range(n):
			arr.append([start[i], end[i]])
		arr.sort(key=lambda x: x[1])
		res = 1
		prevjob = arr[0][1]
		for i in range(1, n):
			if arr[i][0] > prevjob:
				prevjob = arr[i][1]
				res += 1
		return res


class Solution:

	def activitySelection(self, n, s, e):
		a = []
		for i in range(n):
			a.append([e[i], s[i]])
		a.sort()
		k = [a[0]]
		d = a[0]
		for i in range(1, n):
			if d[0] < a[i][1]:
				k.append(a[i])
				d = a[i]
		return len(k)


class Solution:

	def activitySelection(self, n, start, end):
		tarr = []
		for i in range(n):
			tarr.append((start[i], end[i]))
		tarr.sort(key=lambda a: a[1])
		count = 1
		curr = tarr[0]
		for i in range(1, n):
			if curr[1] < tarr[i][0]:
				count += 1
				curr = tarr[i]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		if n == 0:
			return 0
		(ss, se) = zip(*sorted(zip(start, end), key=lambda x: x[1]))
		count = 1
		end = se[0]
		for i in range(1, len(ss)):
			if ss[i] > end:
				count += 1
				end = se[i]
		return count


from heapq import heappush, heappop

class Solution:

	def activitySelection(self, n, start, end):
		heap = []
		for i in range(n):
			heappush(heap, [end[i], start[i]])
		(ans, last) = (0, -1)
		while heap:
			temp = heappop(heap)
			if temp[1] > last:
				last = temp[0]
				ans += 1
		return ans


class Solution:

	def activitySelection(self, n, start, end):
		data = [[a, b] for (a, b) in zip(start, end)]
		data.sort(key=lambda x: x[1])
		res = [data[0]]
		for i in range(1, len(data)):
			if res[-1][1] < data[i][0]:
				res.append(data[i])
		return len(res)


class Solution:

	def activitySelection(self, n, start, end):
		arr = []
		for i in range(n):
			arr.append((start[i], end[i]))
		arr.sort(key=lambda x: x[1])
		cnt = 1
		end_time = arr[0][1]
		for i in range(1, n):
			if arr[i][0] > end_time:
				cnt += 1
				end_time = arr[i][1]
		return cnt


class Solution:

	def activitySelection(self, n, start, end):
		arr = sorted(zip(start, end), key=lambda x: x[1])
		t = 0
		c = 0
		for (s, e) in arr:
			if s > t:
				t = e
				c += 1
		return c


from heapq import heappush, heappop, heapify

class Solution:

	def activitySelection(self, n, start, end):
		heap = []
		for i in range(n):
			heappush(heap, [end[i], start[i]])
		count = 1
		pre = heappop(heap)
		while heap:
			cur = heappop(heap)
			if pre[0] < cur[1]:
				count += 1
				pre = cur
		return count


class Solution:

	def activitySelection(self, n, start, end):
		a = []
		for i in range(len(start)):
			a.append([start[i], end[i]])
		a.sort(key=lambda x: x[1])
		c = 1
		for i in range(len(a)):
			start[i] = a[i][0]
			end[i] = a[i][1]
		e = end[0]
		for i in range(len(end)):
			while start[i] > e:
				c += 1
				e = end[i]
		return c


class Solution:

	def activitySelection(self, n, start, end):
		a = []
		for i in range(n):
			a.append([end[i], start[i]])
		a.sort()
		ans = 0
		if a:
			ans = 1
			pre = a[0][0]
		else:
			return 0
		for i in range(1, len(a)):
			if pre < a[i][1]:
				ans += 1
				pre = a[i][0]
		return ans


class Solution:

	def activitySelection(self, n, start, end):
		timings = []
		for (x, y) in zip(start, end):
			timings.append((x, y))
		timings.sort(key=lambda x: x[1])
		count = 1
		res = [timings[0]]
		for i in range(1, len(timings)):
			if timings[i][0] > res[-1][1]:
				count += 1
				res.append(timings[i])
		return count


class Solution:

	def comp(self, i):
		return i[1]

	def activitySelection(self, n, start, end):
		lst = []
		for i in range(n):
			lst.append([start[i], end[i]])
		lst.sort(key=self.comp)
		last = lst[0]
		count = 1
		for i in lst:
			if i[0] <= last[1]:
				continue
			last = i
			count += 1
		return count


class Solution:

	def activitySelection(self, n, start, end):
		l = []
		cnt = 1
		for i in range(n):
			l.append([start[i], end[i]])
		L = sorted(l, key=lambda x: (x[1], x[0]))
		end = L[0][1]
		for i in range(n - 1):
			start = L[i + 1][0]
			if start > end:
				cnt += 1
				end = L[i + 1][1]
		return cnt


class Solution:

	def activitySelection(self, n, start, end):
		mapping = [[0, 0] for i in range(n)]
		for i in range(n):
			mapping[i][0] = start[i]
			mapping[i][1] = end[i]
		out = 0
		mapping.sort()
		last = mapping[0]
		for i in range(1, n):
			curr = mapping[i]
			if curr[0] > last[1]:
				out += 1
				last = curr
			elif curr[0] < last[1] and curr[1] < last[1]:
				last = curr
		return out + 1


class Solution:

	def activitySelection(self, n, start, end):
		intervals = []
		for i in range(n):
			intervals.append((start[i], end[i]))
		intervals = sorted(intervals, key=lambda x: x[1])
		(lastFinish, count) = (0, 0)
		for (s, e) in intervals:
			if s > lastFinish:
				count += 1
				lastFinish = e
		return count


class Solution:

	def activitySelection(self, n, start, end):
		activities = list(zip(start, end))
		activities.sort(key=lambda x: x[1])
		finish = activities[0][1]
		count = 1
		for i in range(1, len(activities)):
			if activities[i][0] > finish:
				count += 1
				finish = activities[i][1]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		A = list(tuple(zip(start, end)))
		A.sort(key=lambda x: x[1])
		activities = 1
		prev_s = A[0][0]
		prev_e = A[0][1]
		for (s, e) in A:
			if s > prev_e:
				activities += 1
				(prev_s, prev_e) = (s, e)
		return activities


class Solution:

	def activitySelection(self, n, start, end):
		sets = []
		for i in range(n):
			sets.append([start[i], end[i]])
		sets.sort(key=lambda x: x[1])
		res = 1
		prev = sets[0][1]
		for i in range(1, n):
			if prev < sets[i][0]:
				res += 1
				prev = sets[i][1]
		return res


class Solution:

	def activitySelection(self, n, start, end):
		time = []
		for i in range(n):
			time.append((end[i], start[i]))
		time.sort()
		prev_end = 0
		count = 0
		for i in range(n):
			start = time[i][1]
			end = time[i][0]
			if start > prev_end:
				count += 1
				prev_end = end
		return count


class Solution:

	def activitySelection(self, n, start, end):
		arr = list(zip(start, end))
		arr = sorted(arr, key=lambda x: x[1])
		c = 1
		i = 0
		for j in range(1, len(arr)):
			if arr[j][0] > arr[i][1]:
				c += 1
				i = j
		return c


from collections import defaultdict

class Solution:

	def activitySelection(self, n, start, end):
		if n <= 1:
			return n
		dic = defaultdict(int)
		for i in range(n):
			if dic[start[i]]:
				dic[start[i]] = min(end[i], dic[start[i]])
			else:
				dic[start[i]] = end[i]
		time = sorted(dic.items(), key=lambda x: (x[1], x[0]))
		time = list(time)
		count = 1
		e = time[0][1]
		for i in range(1, len(time)):
			if time[i][0] > e:
				count += 1
				e = time[i][1]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		ans = []
		for i in range(0, n):
			ans.append([start[i], end[i]])
		ans.sort(key=lambda x: x[1])
		count = 1
		ansend = ans[0][1]
		for i in range(1, n):
			if ans[i][0] > ansend:
				count += 1
				ansend = ans[i][1]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		arr = [[start[i], end[i]] for i in range(n)]
		arr.sort(key=lambda x: x[1])
		res = 1
		prev = 0
		for curr in range(1, n):
			if arr[curr][0] > arr[prev][1]:
				res += 1
				prev = curr
		return res


class Solution:

	def activitySelection(self, n, start, end):
		acts = [(s, e) for (s, e) in zip(start, end)]
		acts = sorted(acts, key=lambda x: x[1])
		count = 1
		end = acts[0][1]
		for j in range(1, len(acts)):
			start = acts[j][0]
			if start > end:
				count += 1
				end = acts[j][1]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		items = []
		for i in range(n):
			items.append((end[i], start[i]))
		items.sort()
		cnt = 0
		time = 0
		for i in range(n):
			(e, s) = items[i]
			if s <= time:
				continue
			time = e
			cnt += 1
		return cnt


class Solution:

	def activitySelection(self, n, start, end):
		l = []
		for i in range(n):
			l.append((start[i], end[i]))
		l.sort(key=lambda x: x[1])
		start = l[0][1]
		total = 1
		for i in range(n):
			if l[i][0] > start:
				total += 1
				start = l[i][1]
		return total


class Solution:

	def activitySelection(self, n, start, end):
		result = []
		act = []
		for i in range(len(start)):
			act.append([start[i], end[i]])

		def mykey(e):
			return e[1]
		act.sort(key=mykey)
		r = act[0][1]
		result.append(act[0])
		for i in range(1, len(act)):
			if act[i][0] > r:
				result.append(act[i])
				r = act[i][1]
		return len(result)


class Solution:

	def activitySelection(self, n, s, e):
		time = []
		for (i, j) in zip(s, e):
			time.append([i, j])
		time.sort(key=lambda x: x[1])
		end = -1
		count = 0
		for (i, j) in time:
			if end < i:
				end = j
				count += 1
		return count


class Solution:

	def activitySelection(self, n, start, end):
		stk = []
		for x in range(len(start)):
			stk.append([start[x], end[x]])
		stk.sort(key=lambda x: x[1])
		total = 1
		(s, e) = stk[0]
		for x in range(1, len(stk)):
			(ss, ee) = stk[x]
			if e + 1 <= ss:
				total += 1
				e = ee
		return total


class Solution:

	def activitySelection(self, n, start, end):
		d = {}
		c = 1
		for i in range(n):
			if end[i] not in d:
				d[end[i]] = start[i]
			elif start[i] > d[end[i]]:
				d[end[i]] = start[i]
		li = end.copy()
		li.sort()
		f = li[0]
		for i in range(n - 1):
			if f < d[li[i + 1]]:
				c += 1
				f = li[i + 1]
		return c


class Solution:

	def activitySelection(self, n, start, end):
		res = []
		for i in range(n):
			res.append([start[i], end[i]])
		res = sorted(res, key=lambda x: (x[1], x[0]))
		count = 0
		end = -546
		for i in range(len(res)):
			if end < res[i][0]:
				end = res[i][1]
				count += 1
		return count


class Solution:

	def activitySelection(self, n, start, end):
		a = [[start[i], end[i]] for i in range(n)]
		a.sort(key=lambda x: (x[1], -x[0]))
		(x, y) = a[0]
		count = 1
		for i in a[1:]:
			if i[0] > y:
				count += 1
				(x, y) = i
		return count


class Solution:

	def activitySelection(self, n, start, end):
		arr = list(zip(start, end))
		arr.sort(key=lambda x: x[1])
		last = arr[0]
		ans = 1
		for i in arr[1:]:
			if i[0] > last[1]:
				ans += 1
				last = i
		return ans


class Solution:

	def activitySelection(self, n, start, end):

		def fun(start, end, n):
			activities = [(start[i], end[i]) for i in range(n)]
			activities.sort(key=lambda x: x[1])
			curr_finish_time = activities[0][1]
			num_activities_selected = 1
			for i in range(1, n):
				if activities[i][0] > curr_finish_time:
					num_activities_selected += 1
					curr_finish_time = activities[i][1]
			return num_activities_selected
		return fun(start, end, n)


class Solution:

	def activitySelection(self, n, start, end):
		d = []
		for i in range(n):
			d.append([start[i], end[i]])
		d.sort(key=lambda x: x[1])
		res = 1
		temp = d[0][1]
		for i in range(1, n):
			if temp < d[i][0]:
				res += 1
				temp = d[i][1]
		return res


class Solution:

	def activitySelection(self, n, start, end):
		l = list(zip(start, end))
		l.sort(key=lambda x: x[1])
		c = 1
		e = l[0][1]
		for i in range(1, len(l)):
			if l[i][0] > e:
				c = c + 1
				e = l[i][1]
		return c


class Solution:

	def activitySelection(self, n, start, end):
		meet = []
		for i in range(n):
			meet.append([end[i], start[i]])
		meet.sort()
		res = 1
		limit = meet[0][0]
		for i in range(1, n):
			if meet[i][1] > limit:
				res += 1
				limit = meet[i][0]
		return res


import heapq

class Solution:

	def activitySelection(self, n, start, end):
		acvitity_list = []
		for (i, val) in enumerate(start):
			acvitity_list.append((end[i], val, i))
		heapq.heapify(acvitity_list)
		act_num = 0
		cur_day = 0
		while len(acvitity_list) > 0:
			act = heapq.heappop(acvitity_list)
			if act[1] > cur_day:
				cur_day = act[0]
				act_num += 1
		return act_num


class Solution:

	def activitySelection(self, n, start, end):
		list = []
		for i in range(0, n):
			list.append((start[i], end[i]))
		list = sorted(list, key=lambda x: x[1])
		ans = 1
		f = list[0][1]
		for i in range(1, n):
			if list[i][0] > f:
				ans += 1
				f = list[i][1]
		return ans


class Solution:

	def activitySelection(self, n, start, end):
		lis = list(zip(start, end))
		lis.sort(key=lambda x: x[1])
		pre = 0
		res = 1
		for curr in range(1, n):
			if lis[curr][0] > lis[pre][1]:
				res += 1
				pre = curr
		return res


class Solution:

	def activitySelection(self, n, start, end):
		l2 = list(zip(start, end))
		l2.sort(key=lambda x: x[1])
		max1 = 0
		last = -1
		for i in l2:
			if i[0] > last:
				max1 += 1
				last = i[1]
		return max1


class Solution:

	def activitySelection(self, n, start, end):
		pairs = [[start[i], end[i]] for i in range(n)]
		pairs.sort(key=lambda x: x[1])
		prev_end = pairs[0][1]
		activities = 1
		for (start, end) in pairs[1:]:
			if start > prev_end:
				prev_end = end
				activities += 1
		return activities


class Solution:

	def activitySelection(self, n, start, end):
		count = 1
		arr = []
		for i in range(n):
			arr.append((end[i], start[i]))
		arr.sort()
		i = 0
		j = 1
		while j < n:
			if arr[j][1] > arr[i][0]:
				count += 1
				i = j
				j += 1
			else:
				j += 1
		return count


class Solution:

	def activitySelection(self, n, start, end):
		meetings = []
		i = 0
		while i < n:
			temp = [i, start[i], end[i]]
			meetings.append(temp)
			i += 1
		meetings.sort(key=lambda x: (x[2], x[0]))
		time = 0
		count = 0
		for i in meetings:
			if time < i[1]:
				count += 1
				time = i[2]
		return count


class Solution:

	def activitySelection(self, n, start, end):
		n = len(end)
		arr = []
		for i in range(n):
			k = [start[i], end[i]]
			arr.append(k)
		arr.sort(key=lambda a: a[1])
		i = 0
		p = 1
		for j in range(1, n):
			if arr[j][0] > arr[i][1]:
				p += 1
				i = j
		return p