There are N events in Geek's city. You are given two arrays start[] and end[] denoting starting and ending day of the events respectively. Event i starts at start[i] and ends at end[i].
You can attend an event i at any day d between start[i] and end[i] (start[i] ≤ d ≤ end[i]). But you can attend only one event in a day.
Find the maximum number of events you can attend.
 
Example 1:
Input:
N = 3
start[] = {1, 2, 1}
end[] = {1, 2, 2}
Output:
2
Explanation:
You can attend a maximum of two events.
You can attend 2 events by attending 1st event
at Day 1 and 2nd event at Day 2.
Example 2:
Input:
N = 3
start[i] = {1, 2, 3}
end[i] = {2, 3, 4} 
Output :
3
Explanation:
You can attend all events by attending event 1
at Day 1, event 2 at Day 2, and event 3 at Day 3.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function maxEvents() which takes an integer N and two arrays start[], and end[] of size N as input parameters and returns the maximum number of events that can be attended by you.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5}
1 ≤ start[i] ≤ end[i] ≤ 10^{5}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def maxEvents(self, start, end, N):

        # code here 

Solutions:
import heapq

class Solution:

	def maxEvents(self, start, end, N):
		A = []
		for i in range(N):
			A.append([start[i], end[i]])
		A.sort(reverse=True)
		h = []
		res = d = 0
		while A or h:
			if not h:
				d = A[-1][0]
			while A and A[-1][0] <= d:
				heapq.heappush(h, A.pop()[1])
			heapq.heappop(h)
			res += 1
			d += 1
			while h and h[0] < d:
				heapq.heappop(h)
		return res


class Solution:

	def maxEvents(self, start, end, n):
		ans = []
		for i in range(n):
			ans.append([start[i], end[i]])
		ans.sort()
		arr = [0 for i in range(max(end) + 1)]
		for i in range(n - 1, -1, -1):
			j = ans[i][1]
			while j >= ans[i][0]:
				if j < len(arr):
					if arr[j] == 0:
						arr[j] = 1
						break
				j = j - 1
		return sum(arr)


class Solution:

	def maxEvents(self, start, end, N):
		events = list(zip(start, end))
		events.sort()
		s = {}
		for i in range(N - 1, -1, -1):
			if not events[i][1] in s:
				s[events[i][1]] = 1
			else:
				e = events[i][1]
				while e >= events[i][0]:
					if not e in s:
						s[e] = 1
						break
					e -= 1
		return len(s)


from heapq import *

class Solution:

	def maxEvents(self, start, end, N):
		ret = []
		for (s, e) in zip(start, end):
			ret.append([s, e])
		hp = []
		heapify(hp)
		ret.sort()
		res = 0
		for x in range(1, 10 ** 5 + 1):
			while ret and ret[0][0] == x:
				cur = ret.pop(0)
				heappush(hp, [cur[1], cur[0]])
			while hp and hp[0][0] < x:
				heappop(hp)
			if hp:
				res += 1
				heappop(hp)
		return res


from collections import deque

class Solution:

	def maxEvents(self, start, end, n):
		end_day_sorted = sorted(end)
		max_day_of_event = end_day_sorted[-1]
		list_of_day = [0] * max_day_of_event
		list_of_events = deque()
		for i in range(n):
			list_of_events.append([start[i], end[i]])
		list_of_events = sorted(list_of_events)
		while list_of_events:
			current_event = list_of_events.pop()
			if list_of_day[current_event[1] - 1] != -1:
				list_of_day[current_event[1] - 1] = -1
			else:
				for i in range(current_event[1], current_event[0] - 1, -1):
					if list_of_day[i - 1] != -1:
						list_of_day[i - 1] = -1
						break
		count_event = 0
		for i in range(len(list_of_day)):
			if list_of_day[i] == -1:
				count_event += 1
		return count_event


class Solution:

	def maxEvents(self, start, end, N):
		l = []
		for i in range(N):
			l.append([start[i], end[i]])
		l.sort(reverse=True)
		d = [-1 for i in range(max(end))]
		for i in range(N):
			for j in range(l[i][1] - 1, l[i][0] - 2, -1):
				if d[j] == -1:
					d[j] = 'b'
					break
		c = 0
		for i in d:
			if i != -1:
				c = c + 1
		return c


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		events = []
		for (s1, e1) in zip(start, end):
			events.append([s1, e1])
		events.sort(key=lambda x: (x[0], x[1]))
		idx = 0
		n = len(events)
		heap = []
		res = 0
		d = events[idx][0]
		while heap or idx < n:
			if not heap:
				d = events[idx][0]
			while idx < n and events[idx][0] <= d:
				heapq.heappush(heap, events[idx][1])
				idx += 1
			heapq.heappop(heap)
			res += 1
			d += 1
			while heap and heap[0] < d:
				heapq.heappop(heap)
		return res


class Solution:

	def maxEvents(self, start, end, N):
		s = set()
		l = []
		for i in range(len(start)):
			l.append([start[i], end[i]])
		l.sort()
		for i in range(N - 1, -1, -1):
			if l[i][1] not in s:
				s.add(l[i][1])
			else:
				e = l[i][1]
				while e >= l[i][0]:
					if e not in s:
						s.add(e)
						break
					e -= 1
		return len(s)


import heapq
import bisect as bs

class Solution:

	def maxEvents(self, a, b, n):
		lst = []
		for i in range(n):
			lst.append((a[i], b[i]))
		lst.sort()
		i = 0
		t = 1
		n = len(lst)
		q = []
		cnt = 0
		tmp1 = 0
		for (x, y) in lst:
			tmp1 = max(tmp1, y)
		while t <= tmp1:
			while i < n and lst[i][0] == t:
				heapq.heappush(q, (lst[i][1], lst[i][0]))
				i += 1
			while len(q) > 0:
				(x, y) = heapq.heappop(q)
				if x >= t:
					cnt += 1
					break
			t += 1
		return cnt


class Solution:

	def maxEvents(self, start, end, N):
		events = []
		for i in range(N):
			events.append((start[i], end[i]))
		days = [0] * (10 ** 5 + 1)
		events.sort(key=lambda x: (-1 * x[0], x[1]))
		count = 0
		for (s, e) in events:
			for day in reversed(range(s, e + 1)):
				if days[day] == 0:
					days[day] = 1
					count += 1
					break
		return count
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		N = int(input())
		start = list(map(int, input().split()))
		end = list(map(int, input().split()))
		ob = Solution()
		print(ob.maxEvents(start, end, N))


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		events = []
		for i in range(len(start)):
			events.append([start[i], end[i]])
		events.sort(key=lambda x: (x[0], x[1]))
		last_day = max([event[1] for event in events])
		curr_day = events[0][0]
		attended = 0
		end_day = []
		i = 0
		while curr_day < last_day + 1:
			while i < len(events) and events[i][0] == curr_day:
				heapq.heappush(end_day, events[i][-1])
				i += 1
			while len(end_day) > 0 and end_day[0] < curr_day:
				heapq.heappop(end_day)
			if len(end_day) > 0:
				heapq.heappop(end_day)
				attended += 1
			curr_day += 1
		return attended


from heapq import *

class Solution:

	def maxEvents(self, start, end, N):
		meetings = []
		for i in range(N):
			meetings.append([start[i], end[i]])
		meetings.sort()
		min_heap = []
		meetings_attended = i = 0
		current_event_day = meetings[0][0]
		while i < N:
			while i < N and meetings[i][0] == current_event_day:
				heappush(min_heap, meetings[i][1])
				i += 1
			heappop(min_heap)
			meetings_attended += 1
			current_event_day += 1
			while min_heap and min_heap[0] < current_event_day:
				heappop(min_heap)
			if i < N and (not min_heap):
				current_event_day = meetings[i][0]
		while min_heap:
			if heappop(min_heap) >= current_event_day:
				current_event_day += 1
				meetings_attended += 1
		return meetings_attended


from collections import defaultdict
import heapq

class Solution:

	def maxEvents(self, start, end, N):
		adj = defaultdict(list)
		for i in range(N):
			if start[i] in adj:
				adj[start[i]].append([start[i], end[i]])
			else:
				adj[start[i]] = [[start[i], end[i]]]
		h = []
		days = 0
		for i in range(1, 100001):
			if i in adj:
				for k in adj[i]:
					heapq.heappush(h, [k[1], k[0]])
			while h and h[0][0] < i:
				heapq.heappop(h)
			if h:
				days += 1
				heapq.heappop(h)
		return days


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		events = []
		for i in range(0, N):
			events.append([start[i], end[i]])
		events.sort(key=lambda x: (x[0], x[1]))
		i = 0
		heap = []
		res = 0
		d = events[i][0]
		while heap or i < N:
			if not heap:
				d = events[i][0]
			while i < N and events[i][0] <= d:
				heapq.heappush(heap, events[i][1])
				i += 1
			heapq.heappop(heap)
			res += 1
			d += 1
			while heap and heap[0] < d:
				heapq.heappop(heap)
		return res


class Solution:

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

	def maxEvents(self, start, end, N):
		event = []
		ma = 0
		for i in range(N):
			event.append([start[i], end[i]])
			ma = max(ma, end[i])
		parent = [0] * (ma + 2)
		for i in range(len(parent)):
			parent[i] = i
		parent[-1] = 0
		count = 0
		event.sort(key=lambda x: (x[1], x[0]))
		for (x, y) in event:
			mytimeslot = self.find(parent, x)
			if mytimeslot <= y and mytimeslot != 0:
				parent[mytimeslot] = parent[mytimeslot + 1]
				count += 1
		return count


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		not_started = []
		started = []
		final_time = 0
		for i in range(N):
			heapq.heappush(not_started, (start[i], end[i]))
			final_time = max(end[i], final_time)
		count = 0
		time = 0
		while time <= final_time:
			while not_started and not_started[0][0] == time:
				event = heapq.heappop(not_started)
				heapq.heappush(started, (event[1], event[0]))
			while started and started[0][0] < time:
				heapq.heappop(started)
			if started:
				heapq.heappop(started)
				count += 1
			time += 1
		return count


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		intervals = [(start[i], end[i]) for i in range(N)]
		intervals.sort()
		minHeap = []
		heapq.heapify(minHeap)
		(day, count, ind) = (0, 0, 0)
		while minHeap or ind < N:
			if len(minHeap) == 0:
				day = intervals[ind][0]
			while ind < N and intervals[ind][0] <= day:
				heapq.heappush(minHeap, intervals[ind][1])
				ind += 1
			count += 1
			day += 1
			heapq.heappop(minHeap)
			while minHeap and minHeap[0] < day:
				heapq.heappop(minHeap)
		return count


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		tmp_list = [None] * N
		for i in range(N):
			tmp_list[i] = (start[i], end[i])
		tmp_list.sort(key=lambda x: x[0])
		min_heap = []
		i = 0
		count = 0
		while i < N or min_heap:
			if not min_heap:
				day = tmp_list[i][0]
			while i < N and tmp_list[i][0] == day:
				heapq.heappush(min_heap, tmp_list[i][1])
				i += 1
			heapq.heappop(min_heap)
			day += 1
			count += 1
			while min_heap and min_heap[0] < day:
				val = heapq.heappop(min_heap)
		return count


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		li1 = []
		for q in range(len(start)):
			li1.append([start[q], end[q]])
		li1.sort(reverse=True)
		h = []
		heapq.heapify(h)
		ans = 0
		d = 0
		while h or li1:
			if len(h) == 0:
				d = li1[-1][0]
			while li1 and li1[-1][0] <= d:
				heapq.heappush(h, li1.pop()[1])
			heapq.heappop(h)
			ans += 1
			d += 1
			while h and h[0] < d:
				heapq.heappop(h)
		return ans


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		events = []
		for (s, e) in zip(start, end):
			events.append((s, e))
		events.sort()
		started = []
		(i, curr_day, count) = (0, events[0][0], 0)
		while i < N:
			while i < N and events[i][0] == curr_day:
				heapq.heappush(started, events[i][1])
				i += 1
			event = heapq.heappop(started)
			count += 1
			curr_day += 1
			while started and started[0] < curr_day:
				heapq.heappop(started)
			if i < N and (not started):
				curr_day = events[i][0]
		while started:
			if heapq.heappop(started) >= curr_day:
				curr_day += 1
				count += 1
		return count


class Solution:

	def maxEvents(self, s, f, n):
		l = []
		for i in range(n):
			l.append((s[i], f[i]))
		ans = set()
		l.sort(key=lambda x: (x[0], x[1]), reverse=True)
		for i in range(n):
			if l[i][1] not in ans:
				ans.add(l[i][1])
			else:
				for k in range(l[i][1], l[i][0] - 1, -1):
					if k not in ans:
						ans.add(k)
						break
		return len(ans)


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		intervals = [(a, b) for (a, b) in zip(start, end)]
		intervals = sorted(intervals)
		events_list = []
		curr_day = 0
		counter = 0
		while len(intervals) > 0 or len(events_list) > 0:
			if len(events_list) == 0:
				curr_day = intervals[0][0]
			while len(intervals) > 0 and intervals[0][0] <= curr_day:
				heapq.heappush(events_list, intervals.pop(0)[1])
			heapq.heappop(events_list)
			counter += 1
			curr_day += 1
			while len(events_list) > 0 and events_list[0] < curr_day:
				heapq.heappop(events_list)
		return counter


class Solution:

	def maxEvents(self, start, end, n):
		lst = []
		st = set()
		for i in range(n):
			a = [start[i], end[i]]
			lst.append(a)
		lst.sort(key=lambda x: (x[0], x[1]), reverse=True)
		for i in range(n):
			if lst[i][1] not in st:
				st.add(lst[i][1])
			else:
				for j in range(lst[i][1], lst[i][0] - 1, -1):
					if j not in st:
						st.add(j)
						break
		return len(st)


class Solution:

	def maxEvents(self, start, end, N):
		sort_e = sorted(range(N), key=lambda x: (end[x], start[x]))
		visited = [False] * (max(end) + 1)
		ans = 0
		day = 0
		for i in sort_e:
			if day >= end[i]:
				continue
			if day + 1 < start[i]:
				test = start[i]
				while test < len(visited) and visited[test] and (test <= end[i]):
					test += 1
				if test <= end[i]:
					ans += 1
					visited[test] = True
			else:
				day += 1
				while day < len(visited) and visited[day] and (day <= end[i]):
					day += 1
				if day <= end[i]:
					ans += 1
					visited[day] = True
		return ans


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		m = max(end)
		h = []
		l = list(zip(start, end))
		i = 0
		d = 0
		l.sort()
		c = 0
		while d <= m:
			if i < N and (not h):
				d = l[i][0]
			while i < N and l[i][0] <= d:
				heapq.heappush(h, l[i][1])
				i += 1
			while h and h[0] < d:
				heapq.heappop(h)
			if h:
				heapq.heappop(h)
				c += 1
			d += 1
		return c


from heapq import heappush, heappop

class Solution:

	def maxEvents(self, start, end, n):
		arr = []
		ans = 0
		for i in range(n):
			arr.append([start[i], end[i]])
		arr.sort(key=lambda x: x[0])
		started = []
		curr = arr[0][0]
		i = 0
		while i < n:
			while i < n and arr[i][0] == curr:
				heappush(started, arr[i][1])
				i += 1
			heappop(started)
			curr += 1
			ans += 1
			while started and started[0] < curr:
				heappop(started)
			if i < n and (not started):
				curr = arr[i][0]
		while started:
			if heappop(started) >= curr:
				ans += 1
				curr += 1
		return ans


class Solution:

	def maxEvents(self, start, end, N):
		if N == 0:
			return 0
		if N == 1:
			return 1
		eventArr = []
		for i in range(N):
			eventArr.append([start[i], end[i]])
		eventArr = sorted(eventArr, key=lambda x: x[0])
		l = set()
		count = 0
		for i in range(N - 1, -1, -1):
			endDate = eventArr[i][1]
			while endDate >= eventArr[i][0]:
				if endDate not in l:
					l.add(endDate)
					count += 1
					break
				endDate -= 1
		return count


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		arr = []
		for i in range(len(end)):
			arr.append([start[i], end[i]])
		arr.sort()
		heap = []
		ans = 0
		cur = 0
		while len(arr) or len(heap) != 0:
			if not len(heap):
				cur = arr[0][0]
			while len(arr) and arr[0][0] == cur:
				heapq.heappush(heap, arr.pop(0)[1])
			heapq.heappop(heap)
			ans += 1
			cur += 1
			while len(heap) and heap[0] < cur:
				heapq.heappop(heap)
		return ans


import heapq

class Solution:

	def maxEvents(self, start, end, N):
		e = []
		for (s, el) in zip(start, end):
			e.append([s, el])
		e.sort(key=lambda x: (x[0], x[1]))
		i = 0
		(n, h, res, d) = (len(e), [], 0, e[i][0])
		while h or i < n:
			if not h:
				d = e[i][0]
			while i < n and e[i][0] <= d:
				heapq.heappush(h, e[i][1])
				i += 1
			heapq.heappop(h)
			res += 1
			d += 1
			while h and h[0] < d:
				heapq.heappop(h)
		return res


import operator, heapq

class Solution:

	def maxEvents(self, start, end, N):
		arr = []
		for (sD, eD) in zip(start, end):
			arr.append((sD, eD))
		arr.sort(key=lambda x: (x[0], x[1]))
		idx = 0
		n = len(arr)
		heap = []
		res = 0
		d = arr[idx][0]
		while heap or idx < n:
			if not heap:
				d = arr[idx][0]
			while idx < n and arr[idx][0] <= d:
				heapq.heappush(heap, arr[idx][1])
				idx += 1
			heapq.heappop(heap)
			res += 1
			d += 1
			while heap and heap[0] < d:
				heapq.heappop(heap)
		return res