There is one meeting room in a firm. There are N meetings in the form of (S[i], F[i]) where S[i] is the start time of meeting i and F[i] is the finish time of meeting i. The task is to find the maximum number of meetings that can be accommodated in the meeting room. You can accommodate a meeting if the start time of the meeting is strictly greater than the finish time of the previous meeting. Print all meeting numbers.
Note: If two meetings can be chosen for the same slot then choose meeting with smaller index in the given array.
 
Example 1:
Input:
N= 6
S = {1,3,0,5,8,5}
F = {2,4,6,7,9,9} 
Output:
{1,2,4,5}
Explanation:
We can attend the 1st meeting from (1 to 2),
then the 2nd meeting from (3 to 4), then the
4th meeting from (5 to 7), and the last meeting
we can attend is the 5th from (8 to 9). It can
be shown that this is the maximum number of
meetings we can attend.
 
Example 2:
Input:
N= 1
S = {3}
F = {7}
Output:
{1}
Explanation:
Since there is only one meeting, we can attend the meeting.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxMeetings() which takes the arrays S[], F[], and its size N as inputs and returns the meeting numbers we can attend in sorted order.
 
Expected Time Complexity: O(N*log(N))
Expected Auxiliary Space: O(N)
 
 
Constraints:
1 <= N <= 10^{5}
1 <= S[i] <= F[i] <= 10^{9}
Sum of N over all test cases doesn't exceeds 10^{6}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms

Starter code: from typing import List





class Solution:

    def maxMeetings(self, N : int, S : List[int], F : List[int]) -> List[int]:

        # code here

        



Solutions:
from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		A = []
		for i in range(N):
			A.append([S[i], F[i], i + 1])
		A.sort(key=lambda x: (x[1], x[2]))
		c = 1
		time = A[0][1]
		ans = [A[0][2]]
		for i in range(1, N):
			if A[i][0] > time:
				c += 1
				ans.append(A[i][2])
				time = A[i][1]
			else:
				pass
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		pairs = []
		for i in range(N):
			pairs.append([S[i], F[i], i + 1])
		pairs.sort(key=lambda x: x[1])
		count = []
		curr = pairs[0][1]
		count.append(pairs[0][2])
		for i in range(1, N):
			if pairs[i][0] > curr:
				count.append(pairs[i][2])
				curr = pairs[i][1]
		count.sort()
		return count


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		lst = list(map(list, zip(S, F)))
		for i in range(len(lst)):
			lst[i].append(i + 1)
		lst.sort(key=lambda x: x[1])
		res = []
		end = 0
		for i in range(len(lst)):
			if lst[i][0] > end:
				res.append(lst[i][2])
				end = lst[i][1]
		return sorted(res)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		if N == 1:
			return [1]
		objects = []
		for i in range(N):
			objects.append([i + 1, S[i], F[i]])
		objects.sort(key=lambda items: [items[1], items[2], items[0]])
		stk = []
		ans = []
		stk.append(objects[0])
		ans.append(objects[0][0])
		for i in range(1, N):
			prevend = stk[-1][2]
			currstart = objects[i][1]
			currend = objects[i][2]
			if currstart > prevend:
				stk.append(objects[i])
				ans.append(objects[i][0])
			elif currend < prevend:
				stk.pop()
				ans.pop()
				stk.append(objects[i])
				ans.append(objects[i][0])
			elif currend == prevend:
				if objects[i][0] < stk[-1][0]:
					stk.pop()
					ans.pop()
					stk.append(objects[i])
					ans.append(objects[i][0])
			else:
				continue
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meeting = [(S[i], F[i], i + 1) for i in range(N)]
		meeting.sort(key=lambda a: a[1])
		maxi = []
		maxi.append(meeting[0][2])
		finish = meeting[0][1]
		for i in range(1, N):
			if meeting[i][0] > finish:
				maxi.append(meeting[i][2])
				finish = meeting[i][1]
		maxi.sort()
		return maxi


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		l = []
		for i in range(N):
			l.append([F[i], S[i], i + 1])
		l.sort()
		en = l[0][0]
		st = l[0][1]
		ans = 1
		c = [l[0][2]]
		for i in range(1, N):
			if en < l[i][1]:
				en = l[i][0]
				ans += 1
				c.append(l[i][2])
		c.sort()
		return c


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meeting = [[i + 1, S[i], F[i]] for i in range(N)]
		meeting.sort(key=lambda i: i[2])
		(temp, res) = (meeting[0], [meeting[0][0]])
		for i in meeting[1:]:
			if temp[2] < i[1]:
				(temp, res) = (i, res + [i[0]])
		return sorted(res)


from typing import List

class Solution:

	def maxMeetings(self, N: int, st: List[int], end: List[int]) -> List[int]:
		dummy_arr = []
		for i in range(N):
			dummy_arr.append([st[i], end[i], i + 1])
		dummy_arr.sort(key=lambda x: x[1])
		ans_end = dummy_arr[0][1]
		res = []
		res.append(dummy_arr[0][2])
		for i in range(1, N):
			if ans_end < dummy_arr[i][0]:
				res.append(dummy_arr[i][2])
				ans_end = dummy_arr[i][1]
		res.sort()
		return res


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		for i in range(N):
			arr.append((S[i], F[i], i + 1))
		orignal_arr = arr[:]
		arr.sort(key=lambda x: x[1])
		ans = [arr[0][2]]
		end_time = arr[0][1]
		for i in range(1, N):
			if arr[i][0] > end_time:
				idx = orignal_arr.index(arr[i]) + 1
				ans.append(arr[i][2])
				end_time = arr[i][1]
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		for i in range(N):
			arr.append([F[i], i])
		arr.sort()
		ans = []
		ans.append(arr[0][1] + 1)
		j = 0
		for i in range(1, N):
			if S[arr[i][1]] > arr[j][0]:
				ans.append(arr[i][1] + 1)
				j = i
		ans.sort()
		return ans


from typing import List
from heapq import heappush, heappop, heapify

class Solution:

	def maxMeetings(self, n: int, start: List[int], end: List[int]) -> List[int]:
		heap = []
		for i in range(n):
			heappush(heap, [end[i], start[i], i])
		ans = []
		pre = heappop(heap)
		ans.append(pre[2] + 1)
		while heap:
			cur = heappop(heap)
			if pre[0] < cur[1]:
				ans.append(cur[2] + 1)
				pre = cur
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meetings = [(i + 1, S[i], F[i]) for i in range(N)]
		meetings = sorted(meetings, key=lambda x: x[2])
		endtime = 0
		res = []
		for meeting in meetings:
			if meeting[1] > endtime:
				res.append(meeting[0])
				endtime = meeting[2]
		res = sorted(res)
		return res


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		time = [(i + 1, S[i], F[i]) for i in range(N)]
		time.sort(key=lambda x: x[2])
		meetings = []
		meetings.append(time[0][0])
		end = time[0][2]
		for i in range(1, N):
			if time[i][1] > end:
				meetings.append(time[i][0])
				end = time[i][2]
		meetings.sort()
		return meetings


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meetings = []
		for i in range(N):
			meetings.append([S[i], F[i], i + 1])
		meetings.sort()
		temp = meetings[0]
		result = [meetings[0][2]]
		for j in range(1, N):
			if meetings[j][0] > temp[1]:
				result.append(meetings[j][2])
				temp = meetings[j]
			elif meetings[j][1] < temp[1]:
				result.pop()
				result.append(meetings[j][2])
				temp = meetings[j]
		result.sort()
		return result


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		for i in range(N):
			arr.append((S[i], F[i], i + 1))
		arr.sort(key=lambda x: x[1])
		count = [arr[0][2]]
		att = arr[0][1]
		for time in range(1, N):
			if arr[time][0] > att:
				count.append(arr[time][2])
				att = arr[time][1]
		count.sort()
		return count


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		items = []
		for i in range(N):
			items.append((S[i], F[i], i + 1))
		items.sort(key=lambda x: x[1])
		cnt = 0
		ans = []
		time = 0
		for i in range(N):
			if time >= items[i][0]:
				continue
			cnt += 1
			ans.append(items[i][2])
			time = items[i][1]
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, n: int, S: List[int], F: List[int]) -> List[int]:
		d = {}
		d_ = {}
		for i in range(n):
			if S[i] not in d.keys():
				d[S[i]] = F[i]
			elif d[S[i]] > F[i]:
				d[S[i]] = F[i]
			s = str(S[i]) + ',' + str(F[i])
			if s not in d_.keys():
				d_[s] = i + 1
		ans = []
		x = 0
		for i in sorted(d.keys()):
			if x == 0:
				key = i
				value = d[i]
				x = 1
			elif i < value and d[i] < value:
				key = i
				value = d[i]
			elif i < value and d[i] == value:
				s1 = str(key) + ',' + str(value)
				s2 = str(i) + ',' + str(value)
				if d_[s1] > d_[s2]:
					key = i
					value = d[i]
			elif i > value:
				s = str(key) + ',' + str(value)
				ans.append(d_[s])
				key = i
				value = d[i]
		s = str(key) + ',' + str(value)
		ans.append(d_[s])
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		time = []
		for i in range(len(S)):
			time.append([F[i], S[i], i + 1])
		time.sort()
		l = []
		timeslot = 0
		for i in range(len(time)):
			if time[i][1] > timeslot:
				l.append(time[i][2])
				timeslot = time[i][0]
		return sorted(l)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		new = []
		for i in range(N):
			new.append([S[i], F[i], i])
		new = sorted(new, key=lambda x: x[1])
		ans = [new[0][2] + 1]
		prev_f = new[0][1]
		prev_s = new[0][0]
		for (s, f, i) in new:
			if s <= prev_f:
				pass
			else:
				ans.append(i + 1)
				prev_f = f
				prev_s = s
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, n: int, start: List[int], end: List[int]) -> List[int]:
		meeting = []
		for i in range(n):
			meeting.append((i + 1, start[i], end[i]))
		meeting.sort(key=lambda elm: elm[2])
		ans = []
		ending = -1
		for i in range(n):
			if meeting[i][1] > ending:
				ans.append(meeting[i][0])
				ending = meeting[i][2]
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, n: int, start: List[int], end: List[int]) -> List[int]:
		meeting = [(start[i], end[i], i + 1) for i in range(len(start))]
		meeting.sort(key=lambda ele: ele[1])
		ans = [meeting[0][2]]
		end = meeting[0][1]
		for i in range(1, len(meeting)):
			start = meeting[i][0]
			if start > end:
				ans.append(meeting[i][2])
				end = meeting[i][1]
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		i = 0
		m = [[s, f, i + 1] for (s, f, i) in zip(S, F, range(len(S)))]
		m.sort(key=lambda x: x[1])
		l = []
		l.append(m[0][2])
		tl = m[0][1]
		for i in range(1, N):
			if m[i][0] > tl:
				l.append(m[i][2])
				tl = m[i][1]
		l.sort()
		return l


from typing import List

class Solution:

	def maxMeetings(self, n: int, start: List[int], end: List[int]) -> List[int]:
		start_end = []
		for i in range(n):
			start_end.append([start[i], end[i], i + 1])
		start_end.sort(key=lambda x: x[1])
		ans = [start_end[0][2]]
		timeEnd = start_end[0][1]
		for i in range(1, n):
			if start_end[i][0] > timeEnd:
				ans.append(start_end[i][2])
				timeEnd = start_end[i][1]
		ans.sort()
		return ans


from typing import List

class meeting:

	def __init__(self, start, end, pos):
		self.start = start
		self.end = end
		self.pos = pos

class Solution:

	def maxMeetings(self, n: int, start: List[int], end: List[int]) -> List[int]:
		meet = [meeting(start[i], end[i], i + 1) for i in range(n)]
		meet.sort(key=lambda x: x.end)
		ans = []
		ans.append(meet[0].pos)
		i = 1
		j = 0
		while i < n:
			if meet[i].start > meet[j].end:
				ans.append(meet[i].pos)
				i += 1
				j = i - 1
			else:
				i += 1
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meetings = [[s, e, i + 1] for (i, (s, e)) in enumerate(zip(S, F))]
		meetings.sort(key=lambda x: (x[1], x[2]))
		ans = [meetings[0][2]]
		end = meetings[0][1]
		for m in meetings:
			if m[0] > end:
				ans.append(m[2])
				end = m[1]
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		a = []
		for i in range(N):
			a.append([F[i], i])
		a = sorted(a)
		x = [a[0][1] + 1]
		for i in range(1, N):
			if S[a[i][1]] > F[x[-1] - 1]:
				x += [a[i][1] + 1]
		x = sorted(x)
		return x


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		lst = []
		lst2 = []
		lst3 = []
		for i in range(N):
			lst.append([S[i], F[i]])
		lst.sort(key=lambda x: x[1])
		endtime = lst[0][1]
		lst2.append(lst[0])
		for i in range(1, len(lst)):
			if lst[i][0] > endtime:
				lst2.append(lst[i])
				endtime = lst[i][1]
		for i in lst2:
			for j in range(N):
				if i == [S[j], F[j]]:
					lst3.append(j + 1)
					break
		lst3.sort()
		return lst3


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meetings = []
		for i in range(N):
			meetings.append((S[i], F[i], i + 1))
		sorted_meetings = sorted(meetings, key=lambda x: (x[1], x[2]))
		last_end_time = sorted_meetings[0][1]
		result = [sorted_meetings[0][2]]
		for i in range(1, N):
			if sorted_meetings[i][0] > last_end_time:
				result.append(sorted_meetings[i][2])
				last_end_time = sorted_meetings[i][1]
		return sorted(result)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meetings = [(S[i], F[i], i) for i in range(N)]
		meetings.sort(key=lambda x: x[1])
		select = []
		last = -1
		for meet in meetings:
			if meet[0] > last:
				select.append(meet[2] + 1)
				last = meet[1]
		return sorted(select)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		for i in range(N):
			arr.append((S[i], F[i], i + 1))
		arr.sort(key=lambda x: x[1])
		j = 0
		res = [arr[0][2]]
		for i in range(1, N):
			if arr[i][0] > arr[j][1]:
				j = i
				res.append(arr[i][2])
		return sorted(res)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		for i in range(N):
			arr.append((S[i], F[i], i + 1))
		arr = sorted(arr, key=lambda x: x[1])
		result = [arr[0][2]]
		ansEnd = arr[0][1]
		for i in range(1, len(arr)):
			(a, b, k) = (arr[i][0], arr[i][1], arr[i][2])
			if a > ansEnd:
				result.append(k)
				ansEnd = b
		return sorted(result)


from typing import List
import numpy as np

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		F = np.array(F)
		S = np.array(S)
		ind = F.argsort()
		S = S[ind]
		F.sort()
		p = 0
		output = [ind[0] + 1]
		for i in range(1, N):
			if S[i] > F[p]:
				p = i
				output.append(ind[i] + 1)
		output.sort()
		return output


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meetings = []
		for i in range(N):
			meetings.append((S[i], F[i], i + 1))
		meetings.sort(key=lambda x: x[1])
		(start, end) = (0, 0)
		ans = []
		for item in meetings:
			if item[0] > end:
				ans.append(item[2])
				(start, end, _) = item
		del meetings
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		for i in range(N):
			arr.append((S[i], F[i], i + 1))
		arr.sort(key=lambda x: x[1])
		result = []
		time = float('-inf')
		for (start, end, i) in arr:
			if time < start:
				result.append(i)
				time = end
		return sorted(result)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meetings = [(i + 1, S[i], F[i]) for i in range(N)]
		meetings.sort(key=lambda x: x[2])
		res = [meetings[0][0]]
		start = meetings[0][1]
		end = meetings[0][2]
		for (idx, s, e) in meetings:
			if s > end:
				res.append(idx)
				start = s
				end = e
		return sorted(res)


from typing import List

class Solution:

	def maxMeetings(self, N: int, s: List[int], f: List[int]) -> List[int]:
		time = []
		for (i, j) in zip(s, f):
			time.append([i, j])
		temp = time[:]
		temp.sort(key=lambda x: x[1])
		end = -1
		ans = set()
		seen = set()
		for (i, j) in enumerate(temp):
			if j[0] > end and j[0] not in seen:
				ans.add((j[0], j[1]))
				end = j[1]
				seen.add(j[0])
		re = []
		for (i, j) in enumerate(time):
			if (j[0], j[1]) in ans:
				re.append(i + 1)
				ans.remove((j[0], j[1]))
		return re


from typing import List

def my(node):
	return node.end

class Node:

	def __init__(self, s, e, i):
		self.start = s
		self.end = e
		self.index = i + 1

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		l = []
		for i in range(N):
			extra = Node(S[i], F[i], i)
			l.append(extra)
		l2 = []
		for i in sorted(l, key=my):
			l2.append(i)
		l = []
		ans = []
		l.append(l2[0])
		ans.append(l2[0].index)
		for i in range(1, N):
			if l[-1].end < l2[i].start:
				ans.append(l2[i].index)
				l.append(l2[i])
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		time = []
		for i in range(N):
			time.append([S[i], F[i]])
		s_time = sorted(time, key=lambda x: x[1])
		meet = [time.index(s_time[0])]
		s = 1
		e = 0
		while s < N:
			if s_time[e][1] < s_time[s][0]:
				meet.append(time.index(s_time[s]))
				e = s
				s = s + 1
			else:
				s = s + 1
		result = sorted([i + 1 for i in meet])
		return result


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		l = []
		t = []
		for i in range(N):
			l.append([F[i], S[i], i + 1])
		l.sort()
		t.append(l[0][2])
		c = 1
		d = l[0][0]
		for i in range(1, N):
			if l[i][1] > d:
				t.append(l[i][2])
				d = l[i][0]
		t.sort()
		return t


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meetings = []
		prevEnd = 0
		l = [(S[i], F[i], i) for i in range(len(S))]
		l.sort(key=lambda x: x[1])
		for (start, end, index) in l:
			if start > prevEnd:
				meetings.append(index + 1)
				prevEnd = end
		return sorted(meetings)


from typing import List

class Node:

	def __init__(self, s, e, ind):
		self.s = s
		self.e = e
		self.ind = ind

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		l = []
		for i in range(N):
			node = Node(S[i], F[i], i + 1)
			l.append(node)
		l.sort(key=lambda x: x.e)
		res = [l[0].ind]
		i = 1
		prev = l[0].e
		for i in range(len(l)):
			if l[i].s > prev:
				res.append(l[i].ind)
				prev = l[i].e
		res.sort()
		return res


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		l = []
		j = 0
		ans = []
		for i in range(N):
			l.append([S[i], F[i], i + 1])
		l.sort(key=lambda val: val[1])
		k = l[0][1]
		ans.append(l[0][2])
		for i in range(1, N):
			if k < l[i][0]:
				ans.append(l[i][2])
				k = l[i][1]
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		l = []
		for i in range(N):
			l.append([F[i], i + 1, S[i]])
		l.sort()
		i = 1
		j = 0
		c = 0
		res = []
		e = l[0][0]
		res.append(l[0][1])
		while i < N:
			if l[i][2] > e:
				res.append(l[i][1])
				e = l[i][0]
				i = i + 1
			else:
				i = i + 1
		res.sort()
		return res


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		l = []
		for i in range(N):
			arr.append([S[i], F[i], i + 1])
		arr.sort(key=lambda x: x[1])
		ans = [arr[0][2]]
		i = 0
		j = 1
		while i != N - 1:
			while j != N:
				if arr[i][1] < arr[j][0]:
					ans.append(arr[j][2])
					i = j
					j += 1
				else:
					j += 1
			if j == N:
				break
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		A = []
		for i in range(N):
			A.append((S[i], F[i], i + 1))
		[first, *A] = sorted(A, key=lambda i: i[1])
		ans = [first[2]]
		prevEnd = first[1]
		for (s, e, i) in A:
			if s > prevEnd:
				ans.append(i)
				prevEnd = e
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		A = [[S[i], F[i], i + 1] for i in range(N)]
		A.sort(key=lambda x: [x[1], x[2], x[0]])
		cnt = 1
		prev = A[0][1]
		i = 1
		ans = [A[0][2]]
		while i < N:
			if A[i][0] > prev:
				cnt += 1
				prev = A[i][1]
				ans.append(A[i][2])
			i += 1
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:

		class Meeting:

			def __init__(self, start, end, pos):
				self.start = start
				self.end = end
				self.pos = pos
		meetings = []
		for i in range(N):
			meeting = Meeting(S[i], F[i], i + 1)
			meetings.append(meeting)
		meetings.sort(key=lambda x: x.end)
		time_limit = -1
		ans = []
		for pair in meetings:
			if pair.start > time_limit:
				time_limit = pair.end
				ans.append(pair.pos)
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		for i in range(N):
			arr.append([S[i], F[i], i + 1])
		ref = set()
		arr.sort()
		(i, j) = (0, 1)
		while j < N:
			(l1, l2) = (arr[i], arr[j])
			if l1[1] >= l2[0]:
				if l1[1] > l2[1]:
					ref.add(l1[2])
					i = j
					j += 1
				elif l1[1] == l2[1]:
					if l1[2] < l2[2]:
						ref.add(l2[2])
						j += 1
					else:
						ref.add(l1[2])
						i = j
						j += 1
				else:
					ref.add(l2[2])
					j += 1
			else:
				i = j
				j += 1
		ans = []
		for i in range(1, N + 1):
			if i not in ref:
				ans.append(i)
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		l = []
		ans = []
		for i in range(len(S)):
			l.append([S[i], F[i], i])
		l.sort(key=lambda x: x[1])
		r = l[0][1]
		ans.append(l[0][2] + 1)
		for i in range(1, len(l)):
			if l[i][0] > r:
				r = l[i][1]
				ans.append(l[i][2] + 1)
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		comb = [(i, S[i], F[i]) for i in range(len(S))]
		comb = sorted(comb, key=lambda x: x[-1])
		resp = [comb[0][0] + 1]
		local = comb[0][2]
		for elem in comb:
			if elem[1] > local:
				resp.append(elem[0] + 1)
				local = elem[2]
		return sorted(resp)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]):
		inter = []
		for i in range(N):
			inter.append([F[i], i])
		inter.sort(key=lambda x: x[0])
		count = []
		first = inter[0][0]
		count.append(inter[0][1] + 1)
		for i in range(1, N):
			if S[inter[i][1]] > first:
				count.append(inter[i][1] + 1)
				first = inter[i][0]
		count.sort()
		return count


from typing import List

class Solution:

	def maxMeetings(self, n: int, start: List[int], end: List[int]) -> List[int]:
		inter = []
		for i in range(n):
			inter.append([end[i], i])
		inter.sort(key=lambda x: x[0])
		count = []
		first = inter[0][0]
		count.append(inter[0][1] + 1)
		for i in range(1, n):
			if start[inter[i][1]] > first:
				count.append(inter[i][1] + 1)
				first = inter[i][0]
		count.sort()
		return count


from typing import List

class Solution:

	def maxMeetings(self, n: int, start: List[int], end: List[int]) -> List[int]:
		l = []
		ans = []
		for i in range(n):
			l.append([start[i], end[i], i + 1])
		arr = l.sort(key=lambda i: i[1])
		count = 1
		s = l[0][0]
		e = l[0][1]
		ans.append(l[0][2])
		for i in range(1, n):
			if l[i][0] > e:
				ans.append(l[i][2])
				e = l[i][1]
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meet = [[i + 1, S[i], F[i]] for i in range(N)]
		meet.sort(key=lambda x: x[2])
		res = [meet[0][0]]
		end = meet[0][2]
		for i in range(1, len(meet)):
			if meet[i][1] > end:
				res.append(meet[i][0])
				end = meet[i][2]
		res.sort()
		return res


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		meet = []
		for i in range(N):
			l1 = []
			l1.append(S[i])
			l1.append(F[i])
			l1.append(i + 1)
			meet.append(l1)
		meet.sort(key=lambda x: x[1])
		count = [meet[0][-1]]
		prev = meet[0][1]
		for i in range(1, N):
			if meet[i][0] > prev:
				count.append(meet[i][-1])
				prev = meet[i][1]
		return sorted(count)


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		d = {}
		for i in range(N):
			d[i] = [S[i], F[i]]
		lst = sorted(d.items(), key=lambda x: x[1][1])
		ans = [lst[0][0] + 1]
		last_finish = lst[0][1][1]
		for i in range(1, N):
			if lst[i][1][0] > last_finish:
				ans.append(lst[i][0] + 1)
				last_finish = lst[i][1][1]
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		for i in range(N):
			arr.append([S[i], F[i], i + 1])
		arr.sort(key=lambda x: x[1])
		ansst = 0
		ansend = 0
		out = []
		for i in range(0, N):
			s = arr[i][0]
			e = arr[i][1]
			idx = arr[i][2]
			if s > ansend:
				ansend = e
				out.append(idx)
		out.sort()
		return out


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		temp = []
		for i in range(N):
			temp.append([S[i], F[i], i + 1])
		temp.sort(key=lambda x: x[1])
		endtime = temp[0][1]
		ans = [temp[0][2]]
		for i in range(1, N):
			if temp[i][0] > endtime:
				ans.append(temp[i][2])
				endtime = temp[i][1]
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		target_arr = []
		for i in range(N):
			temp = [S[i], F[i], i + 1]
			target_arr.append(temp)
		a = sorted(target_arr, key=lambda x: x[1])
		res = [a[0][2]]
		finish = a[0][1]
		for i in range(N - 1):
			if finish < a[i + 1][0]:
				finish = a[i + 1][1]
				res.append(a[i + 1][2])
		res.sort()
		return res


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		arr = []
		ans = []
		for i in range(N):
			arr.append([S[i], F[i], i + 1])
		arr = sorted(arr, key=lambda x: x[1])
		end = arr[0][1]
		ans.append(arr[0][2])
		for i in range(1, N):
			if arr[i][0] > end:
				ans.append(arr[i][2])
				end = arr[i][1]
		return sorted(ans)


from typing import List

class Solution:

	def maxMeetings(self, n: int, start: List[int], end: List[int]) -> List[int]:
		l = []
		j = 0
		ans = []
		for i in range(n):
			l.append([start[i], end[i], i + 1])
		l.sort(key=lambda x: x[1])
		k = l[0][1]
		ans.append(l[0][2])
		for i in range(1, n):
			if k < l[i][0]:
				ans.append(l[i][2])
				k = l[i][1]
		ans.sort()
		return ans


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		time = []
		for i in range(N):
			time.append((i + 1, S[i], F[i]))
		time.sort(key=lambda x: x[2])
		res = [(0, -1, -1)]
		for (idx, st, end) in time:
			if st > res[-1][2]:
				res.append((idx, st, end))
		res.pop(0)
		return sorted([i[0] for i in res])


from typing import List

class Solution:

	def maxMeetings(self, N: int, s: List[int], e: List[int]) -> List[int]:
		meeting_list = []
		for i in range(N):
			meeting_list.append([s[i], e[i], i + 1])
		meeting_list.sort(key=lambda x: x[1])
		max_end_time = meeting_list[0][1]
		res = [meeting_list[0][2]]
		for i in range(1, N):
			if meeting_list[i][0] > max_end_time:
				max_end_time = meeting_list[i][1]
				res.append(meeting_list[i][2])
		res.sort()
		return res


from typing import List

class Solution:

	def maxMeetings(self, N: int, S: List[int], F: List[int]) -> List[int]:
		ind = []
		for i in range(N):
			ind.append(i)
		ind.sort(key=lambda i: F[i])
		ans = [ind[0]]
		for i in range(1, N):
			current = ind[i]
			last = ans[-1]
			if S[current] > F[last]:
				ans.append(current)
			else:
				continue
		for i in range(len(ans)):
			ans[i] += 1
		return sorted(ans)