You are given n-platform and two main running railway tracks for both directions. Trains that need to stop at your station must occupy one platform for their stoppage and the trains which need not stop at your station will run away through either of the main track without stopping. Now, each train has three values first arrival time, second departure time, and the third required platform number. We are given m such trains you have to tell the maximum number of trains for which you can provide stoppage at your station.
Note: Trains are given in the form of {arrival time, departure time, platform Number} and the arrival time and departure time are represented by a 4-digit integer as 1030 will represent 10:30 and 912 will represent 09:12 (24 hour Clock).
Example 1:
Input : n = 3, m = 6 
Train no.|  Arrival Time |Dept. Time | Platform No.
    1    |   10:00       |  10:30    |    1
    2    |   10:10       |  10:30    |    1
    3    |   10:00       |  10:20    |    2
    4    |   10:30       |  12:30    |    2
    5    |   12:00       |  12:30    |    3
    6    |   09:00       |  10:05    |    1
Output : Maximum Stopped Trains = 5
Explanation : If train no. 1 will left 
to go without stoppage then 2 and 6 can 
easily be accommodated on platform 1. 
And 3 and 4 on platform 2 and 5 on platform 3.
Your Task:
You don't need to read input or print anything. Your task is to complete the function maxStop() which takes two integers n no of platforms, m number of trains, and array trains[] as input parameter and returns an integer. 
Expected Time Complexity: O(M*logM)
Expected Auxiliary Space: O(M)
Constraints:
1 <= N <= 100
1 <= M <= 10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM

Starter code: class Solution():

    def maxStop(self, n, m, trains):

        #your code goes here

Solutions:
class Solution:

	def maxStop(self, n, m, trains):
		plateforms = [[] for i in range(n)]
		for i in range(m):
			plateforms[trains[i][2] - 1].append(trains[i])
		ans = 0
		for plateform in plateforms:
			plateform.sort(key=lambda x: x[1])
			prevStart = -1
			for train in plateform:
				if train[0] >= prevStart:
					ans += 1
					prevStart = train[1]
		return ans


class Solution:

	def maxStop(self, n, m, trains):

		def activity(lst):
			j = 0
			st = 1
			lst.sort(key=lambda x: x[1])
			for i in range(1, len(lst)):
				if lst[i][0] >= lst[j][1]:
					st += 1
					j = i
			return st
		plt = []
		st = 0
		for i in range(m):
			plt.append(trains[i][2])
		for i in range(n):
			c = plt.count(i + 1)
			if c > 1:
				lst = []
				for j in range(m):
					if trains[j][2] == i + 1:
						lst.append(trains[j])
				st += activity(lst)
			elif c == 1:
				st += 1
		return st


class Solution:

	def maxStop(self, n, m, trains):
		count = 0
		arr = [-1] * (n + 1)
		trains.sort(key=lambda i: i[1])
		for i in range(m):
			if arr[trains[i][2]] == -1:
				count += 1
				arr[trains[i][2]] = trains[i]
			elif arr[trains[i][2]][1] <= trains[i][0]:
				arr[trains[i][2]] = trains[i]
				count += 1
		return count


class Solution:

	def maxStop(self, n, m, trains):
		dic = {}
		for each in trains:
			if each[2] not in dic:
				dic[each[2]] = [[each[0], each[1]]]
			else:
				dic[each[2]].append([each[0], each[1]])
		for (a, b) in dic.items():
			b.sort(key=lambda x: x[1])
		res = 0
		for (j, k) in dic.items():
			if k == 1:
				res += 1
			else:
				data = [k[0]]
				for ind in range(1, len(k)):
					if k[ind][0] >= data[-1][1]:
						data.append(k[ind])
				res += len(data)
		return res


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		max_count = 0
		plt_occ = [-1] * n
		for i in range(m):
			if plt_occ[trains[i][2] - 1] == -1:
				max_count += 1
				plt_occ[trains[i][2] - 1] = [trains[i][0], trains[i][1]]
			elif plt_occ[trains[i][2] - 1][1] <= trains[i][0]:
				max_count += 1
				plt_occ[trains[i][2] - 1] = [trains[i][0], trains[i][1]]
		return max_count


class Solution:

	def maxStop(self, n, m, t):
		a = [-1] * (n + 1)
		t.sort(key=lambda i: i[1])
		cnt = 0
		for i in range(m):
			if a[t[i][2]] == -1 or a[t[i][2]][1] <= t[i][0]:
				cnt += 1
				a[t[i][2]] = t[i]
		return cnt


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		end_times = [0] * n
		ans = 0
		for (arrival, departure, platform) in trains:
			if end_times[platform - 1] <= arrival:
				end_times[platform - 1] = departure
				ans += 1
		return ans


class Solution:

	def maxStop(self, n, m, trains):
		d = {}
		for i in trains:
			(arr, dep, p) = (i[0], i[1], i[2])
			if not d.get(p):
				d[p] = []
			d[p].append([arr, dep])
		ans = 0
		for i in d:
			d[i].sort(key=lambda x: x[1])
			curr = d[i][0][1]
			ans += 1
			for j in d[i][1:]:
				if j[0] >= curr:
					ans += 1
					curr = j[1]
		return ans


class Solution:

	def maxStop(self, n, m, trains):
		plat = 0
		for i in range(m):
			if trains[i][2] > plat:
				plat = trains[i][2]
		arr = [-1 for i in range(plat + 1)]
		trains.sort(key=lambda j: j[1])
		cnt = 0
		for i in range(m):
			platform = trains[i][2]
			departure = trains[i][1]
			arrival = trains[i][0]
			if arr[platform] == -1 or arrival >= arr[platform]:
				cnt += 1
				arr[platform] = departure
		return cnt


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		platformsOccupy = [-1 for _ in range(n + 1)]
		totalTrains = 0
		for (arrivalTime, deptTime, platformNo) in trains:
			if platformsOccupy[platformNo] == -1 or arrivalTime >= platformsOccupy[platformNo][1]:
				totalTrains += 1
				platformsOccupy[platformNo] = [arrivalTime, deptTime, platformNo]
		return totalTrains


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda train: train[1])
		max_train = 0
		last_dept_times = [-1] * (n + 1)
		for i in range(m):
			(arrival, dept, platform) = trains[i]
			if arrival >= last_dept_times[platform]:
				last_dept_times[platform] = dept
				max_train += 1
		return max_train


class Solution:

	def maxStop(self, n, m, trains):
		dct = {}
		max_stop_trains = 0
		for ele in trains:
			if ele[2] not in dct:
				dct[ele[2]] = []
				dct[ele[2]].append(ele)
			else:
				dct[ele[2]].append(ele)
		for items in dct:
			dct[items].sort(key=lambda x: x[1])
		for key in dct:
			if len(dct[key]) == 1:
				max_stop_trains += 1
				continue
			max_stop_trains += 1
			last_stop_time = dct[key][0][1]
			for ele in dct[key][1:]:
				if ele[0] < last_stop_time:
					continue
				else:
					max_stop_trains += 1
					last_stop_time = ele[1]
		return max_stop_trains


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		d = {}
		c = 0
		for i in trains:
			if i[2] not in d:
				d[i[2]] = [i[0], i[1]]
				c += 1
			elif d[i[2]][1] <= i[0]:
				d[i[2]] = [i[0], i[1]]
				c += 1
		return c


class Solution:

	def maxStop(self, n, m, train):
		train.sort(key=lambda k: k[1])
		(count, temp) = (0, [-1] * (n + 1))
		for i in train:
			if temp[i[2]] == -1 or temp[i[2]] <= i[0]:
				(temp[i[2]], count) = (i[1], count + 1)
		return count


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		platform = []
		for i in range(n):
			platform.append([0, 0])
		count = 0
		for i in range(m):
			arrival = trains[i][0]
			dept = trains[i][1]
			station = trains[i][2]
			if platform[station - 1] == [0, 0]:
				platform[station - 1] = [arrival, dept]
				count += 1
			else:
				(start, end) = platform[station - 1]
				if arrival >= end:
					platform[station - 1] = [arrival, dept]
					count += 1
		return count


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		ans = 0
		s = [-1] * (n + 1)
		for i in range(m):
			if s[trains[i][2]] == -1:
				ans += 1
				s[trains[i][2]] = trains[i]
			elif s[trains[i][2]][1] <= trains[i][0]:
				s[trains[i][2]] = trains[i]
				ans += 1
		return ans


class Solution:

	def maxStop(self, n, m, trains):
		platform = [-1] * (n + 1)
		trains.sort(key=lambda x: x[1])
		maxtrains = 0
		for i in range(m):
			if platform[trains[i][2]] == -1 or platform[trains[i][2]] <= trains[i][0]:
				maxtrains += 1
				platform[trains[i][2]] = trains[i][1]
		return maxtrains


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		count = 0
		dt = {}
		for i in trains:
			if i[2] not in dt:
				dt[i[2]] = [i[0], i[1]]
				count += 1
			elif dt[i[2]][1] <= i[0]:
				dt[i[2]] = [i[0], i[1]]
				count += 1
		return count


class Solution:

	def maxStop(self, n, m, trains):
		plat = [-1 for _ in range(n + 1)]

		def my_cmp(a, b):
			if a[1] > b[1]:
				return 1
			elif a[1] < b[1]:
				return -1
			else:
				return 0
		import functools
		trains.sort(key=functools.cmp_to_key(my_cmp))
		count = 0
		for t in trains:
			(arr, dept, pt) = t
			if plat[pt] == -1 or arr >= plat[pt][1]:
				count += 1
				plat[pt] = (arr, dept)
		return count


class Solution:

	def maxStop(self, n, m, trains):
		plat = [-1 for i in range(n + 1)]
		time = [-1 for j in range(n + 1)]
		trains.sort(key=lambda j: j[1])
		cnt = 0
		for i in range(m):
			platNo = trains[i][2]
			arr = trains[i][0]
			dep = trains[i][1]
			if plat[platNo] == -1:
				plat[platNo] = 1
				time[platNo] = dep
				cnt += 1
			else:
				avail = time[platNo]
				if arr >= avail:
					time[platNo] = dep
					cnt += 1
		return cnt


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		arr = [-1] * (n + 1)
		c = 0
		for (a, d, p) in trains:
			if arr[p] == -1:
				c += 1
				arr[p] = (a, d)
			elif arr[p][1] <= a:
				c += 1
				arr[p] = (a, d)
		return c


class Solution:

	def maxStop(self, n, m, trains):
		plateforms = [[] for i in range(n)]
		for i in range(m):
			plateforms[trains[i][2] - 1].append(trains[i])
		ans = 0
		for plateform in plateforms:
			plateform.sort(key=lambda x: x[1])
			prevStart = -1
			for train in plateform:
				if train[0] >= prevStart:
					ans += 1
					prevStart = train[1]
		return ans
if __name__ == '__main__':
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		trains = []
		for i in range(m):
			trains.append([int(i) for i in input().split()])
		print(Solution().maxStop(n, m, trains))


class Solution:

	def maxStop(self, n, m, arr):
		arr.sort(key=lambda i: i[1])
		v = [-1] * (n + 1)
		count = 0
		for i in range(m):
			if v[arr[i][2]] == -1:
				count += 1
				v[arr[i][2]] = arr[i]
			elif v[arr[i][2]][1] <= arr[i][0]:
				v[arr[i][2]] = arr[i]
				count += 1
		return count
if __name__ == '__main__':
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		trains = []
		for i in range(m):
			trains.append([int(i) for i in input().split()])
		print(Solution().maxStop(n, m, trains))


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		a = [0] * n
		c = 0
		for t in trains:
			if a[t[2] - 1] == 0:
				a[t[2] - 1] = t[1]
			elif t[0] < a[t[2] - 1]:
				c = c + 1
			else:
				a[t[2] - 1] = t[1]
		return m - c
if __name__ == '__main__':
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		trains = []
		for i in range(m):
			trains.append([int(i) for i in input().split()])
		print(Solution().maxStop(n, m, trains))


class Solution:

	def maxStop(self, n, m, trains):
		trains.sort(key=lambda x: x[1])
		trains.sort(key=lambda x: x[2])
		ans = 1
		pdep = trains[0][1]
		pplt = trains[0][2]
		for i in range(1, m):
			arv = trains[i][0]
			plt = trains[i][2]
			dep = trains[i][1]
			if plt == pplt:
				if arv >= pdep:
					ans += 1
					pdep = dep
			else:
				ans += 1
				pplt = plt
				pdep = dep
		return ans
if __name__ == '__main__':
	for _ in range(int(input())):
		(n, m) = map(int, input().split())
		trains = []
		for i in range(m):
			trains.append([int(i) for i in input().split()])
		print(Solution().maxStop(n, m, trains))


class Solution:

	def maxStop(self, n, m, trains):
		res = 0
		l = [-1 for i in range(n + 1)]
		trains.sort(key=lambda i: i[1])
		for i in range(m):
			if l[trains[i][2]] == -1:
				res += 1
				l[trains[i][2]] = trains[i]
			elif l[trains[i][2]][1] <= trains[i][0]:
				l[trains[i][2]] = trains[i]
				res += 1
		return res


class Solution:

	def maxStop(self, n, m, trains):
		arr_n = [None] * n
		trains.sort(key=lambda x: x[1])
		count = 0
		for i in range(m):
			if arr_n[trains[i][2] - 1] == None:
				count += 1
				arr_n[trains[i][2] - 1] = trains[i][1]
			elif arr_n[trains[i][2] - 1] <= trains[i][0]:
				count += 1
				arr_n[trains[i][2] - 1] = trains[i][1]
			else:
				continue
		return count


class Solution:

	def maxStop(self, n, m, trains):
		arr = sorted(trains, key=lambda x: x[1])
		station = [True] * (n + 1)
		take = 0
		for i in range(len(arr)):
			if station[arr[i][2]] == True:
				station[arr[i][2]] = arr[i][1]
				take += 1
			elif station[arr[i][2]] <= arr[i][0]:
				station[arr[i][2]] = arr[i][1]
				take += 1
		return take