Given arrival and departure times of all trains that reach a railway station. Find the minimum number of platforms required for the railway station so that no train is kept waiting.
Consider that all the trains arrive on the same day and leave on the same day. Arrival and departure time can never be the same for a train but we can have arrival time of one train equal to departure time of the other. At any given instance of time, same platform can not be used for both departure of a train and arrival of another train. In such cases, we need different platforms.
Example 1:
Input: n = 6 
arr[] = {0900, 0940, 0950, 1100, 1500, 1800}
dep[] = {0910, 1200, 1120, 1130, 1900, 2000}
Output: 3
Explanation: 
Minimum 3 platforms are required to 
safely arrive and depart all trains.
Example 2:
Input: n = 3
arr[] = {0900, 1100, 1235}
dep[] = {1000, 1200, 1240}
Output: 1
Explanation: Only 1 platform is required to 
safely manage the arrival and departure 
of all trains. 
Your Task:
You don't need to read input or print anything. Your task is to complete the function findPlatform() which takes the array arr[] (denoting the arrival times), array dep[] (denoting the departure times) and the size of the array as inputs and returns the minimum number of platforms required at the railway station such that no train waits.
Note: Time intervals are in the 24-hour format(HHMM) , where the first two characters represent hour (between 00 to 23 ) and the last two characters represent minutes (this may be > 59).
Expected Time Complexity: O(nLogn)
Expected Auxiliary Space: O(n)
Constraints:
1 ≤ n ≤ 50000
0000 ≤ A[i] ≤ D[i] ≤ 2359

Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms
Skill types: Sorting

Data structures

Greedy algorithms
Expected Time Complexity: O(nLogn)
Expected Auxiliary Space: O(n)

Starter code:
#User function Template for python3



class Solution:    

    #Function to find the minimum number of platforms required at the

    #railway station such that no train waits.

    def minimumPlatform(self,n,arr,dep):

        # code here

Solutions:
from heapq import heapify, heappop, heappush

class Solution:

	def minimumPlatform(self, n, arr, dep):
		train = list(zip(arr, dep))
		train.sort(key=lambda x: x[0])
		ans = 1
		h = []
		heapify(h)
		for i in range(n):
			(s, e) = train[i]
			earliest = heappop(h) if h else -1
			if earliest >= s:
				ans += 1
				heappush(h, earliest)
			heappush(h, e)
		return ans


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr = sorted(arr)
		dep = sorted(dep)
		(i, j, platform, result) = (1, 0, 1, 1)
		while i < n and j < n:
			if arr[i] <= dep[j]:
				i += 1
				platform += 1
			else:
				platform -= 1
				j += 1
			if platform > result:
				result = platform
		return result


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		platforms_needed = 1
		max_platforms = 1
		i = 1
		j = 0
		while i < n and j < n:
			if arr[i] <= dep[j]:
				platforms_needed += 1
				i += 1
				if platforms_needed > max_platforms:
					max_platforms = platforms_needed
			else:
				platforms_needed -= 1
				j += 1
		return max_platforms


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		count = 0
		max_count = 0
		arr_ptr = 0
		dep_ptr = 0
		while arr_ptr < n:
			if arr[arr_ptr] <= dep[dep_ptr]:
				count += 1
				arr_ptr += 1
			else:
				count -= 1
				dep_ptr += 1
			max_count = max(max_count, count)
		return max_count


class Solution:

	def minimumPlatform(self, n, arr, dep):
		platform = [0 for i in range(2361)]
		for i in range(n):
			platform[arr[i]] += 1
			platform[dep[i] + 1] -= 1
		minplatform = 1
		for i in range(1, 2361):
			platform[i] = platform[i] + platform[i - 1]
			minplatform = max(minplatform, platform[i])
		return minplatform


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		p = 1
		result = 1
		i = 1
		j = 0
		while i < n and j < n:
			if arr[i] <= dep[j]:
				p += 1
				i += 1
			elif arr[i] >= dep[j]:
				p -= 1
				j += 1
			if p > result:
				result = p
		return result


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		maxi = 1
		platform = 1
		i = 1
		j = 0
		while i < len(arr) and j < len(arr):
			if arr[i] <= dep[j]:
				platform += 1
				maxi = max(maxi, platform)
				i += 1
			elif dep[j] < arr[i]:
				platform -= 1
				j += 1
		return maxi


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		(i, j, ans) = (0, 0, 0)
		while i < n:
			if arr[i] <= dep[j]:
				ans += 1
				i += 1
			else:
				i += 1
				j += 1
		return ans


class Solution:

	def minimumPlatform(self, n, arr, dep):
		import heapq
		schdule = []
		for i in range(n):
			schdule.append([arr[i], dep[i]])
		schdule.sort(key=lambda x: x[0])
		pq = []
		pq.append(schdule[0][1])
		i = 1
		while i < n:
			start_time = schdule[i][0]
			if start_time <= pq[0]:
				heapq.heappush(pq, schdule[i][1])
			else:
				heapq.heappop(pq)
				heapq.heappush(pq, schdule[i][1])
			i += 1
		return len(pq)


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		(i, j) = (0, 0)
		ans = 0
		count = 0
		while i < len(arr) and j < len(dep):
			if arr[i] <= dep[j]:
				count += 1
				ans = max(ans, count)
				i += 1
			else:
				count -= 1
				j += 1
		return ans


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		platform_needed = 1
		current_platform = 1
		i = 1
		j = 0
		while i < n and j < n:
			if arr[i] <= dep[j]:
				current_platform += 1
				i += 1
			else:
				current_platform -= 1
				j += 1
			platform_needed = max(platform_needed, current_platform)
		return platform_needed


from heapq import heappush, heappop

class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		platforms = 0
		minHeap = []
		for i in range(n):
			arrivalTime = arr[i]
			if minHeap and arrivalTime > minHeap[0]:
				heappop(minHeap)
			else:
				platforms += 1
			heappush(minHeap, dep[i])
		return platforms


class Solution:

	def minimumPlatform(self, n, arr, dep):
		cnt = [0] * 2401
		for i in range(0, n):
			cnt[arr[i]] += 1
			cnt[dep[i] + 1] -= 1
		for i in range(1, 2400):
			cnt[i] += cnt[i - 1]
		return max(cnt)


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		(i, j, cou, m1) = (0, 0, 0, 0)
		while i < n:
			if arr[i] <= dep[j]:
				i += 1
				cou += 1
				m1 = max(m1, cou)
			else:
				j += 1
				cou -= 1
		return m1


class Solution:

	def minimumPlatform(self, n, arr, dep):
		order = []
		for i in range(n):
			order.append([arr[i], 'a'])
			order.append([dep[i], 'd'])
		order.sort(key=lambda x: x[1])
		order.sort()
		result = 1
		plat_needed = 0
		for i in order:
			if i[1] == 'a':
				plat_needed += 1
			else:
				plat_needed -= 1
			result = max(result, plat_needed)
		return result


class Solution:

	def minimumPlatform(self, n, arr, dep):
		max_plat = 1
		required = 1
		arr.sort()
		dep.sort()
		i = 1
		j = 0
		while i < n and j < n:
			if dep[j] < arr[i]:
				max_plat -= 1
				j += 1
			elif dep[j] >= arr[i]:
				i += 1
				max_plat += 1
				required = max(max_plat, required)
		return required


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		platNeeded = 1
		res = 1
		i = 1
		j = 0
		while i < n and j < n:
			if arr[i] <= dep[j]:
				platNeeded += 1
				i += 1
			else:
				platNeeded -= 1
				j += 1
			res = max(res, platNeeded)
		return res


class Solution:

	def minimumPlatform(self, n, arr, dep):
		max = 1
		cur = 1
		ai = 1
		di = 0
		arr.sort()
		dep.sort()
		while ai < n:
			if arr[ai] <= dep[di]:
				ai += 1
				cur += 1
				if cur > max:
					max = cur
			else:
				cur -= 1
				di += 1
		return max


class Solution:

	def minimumPlatform(self, n, arr, dep):
		freq = [0 for _ in range(2500)]
		for i in range(n):
			(l, r) = (arr[i], dep[i])
			freq[l] += 1
			freq[r + 1] -= 1
		ans = 0
		cur = 0
		for num in freq:
			cur += num
			ans = max(ans, cur)
		return ans


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr = sorted(arr)
		dep = sorted(dep)
		times = []
		for i in arr:
			times.append([i, 'a'])
		for i in dep:
			times.append([i, 'd'])
		times = sorted(times, key=lambda x: x[0])
		platforms = 0
		result = 0
		for i in times:
			if i[1] == 'a':
				platforms += 1
				result = max(result, platforms)
			else:
				platforms -= 1
		return result


class Solution:

	def minimumPlatform(self, n, arr, dep):
		count = 0
		max_platform = 0
		dep_ind = 0
		arr_ind = 0
		arr.sort()
		dep.sort()
		while arr_ind < n:
			if arr[arr_ind] <= dep[dep_ind]:
				count += 1
				arr_ind += 1
			elif arr[arr_ind] > dep[dep_ind]:
				count -= 1
				dep_ind += 1
			max_platform = max(max_platform, count)
		return max_platform


import heapq

class Solution:

	def minimumPlatform(self, n, arr, dep):

		def conv(arr):
			if arr == 0:
				arr = '0000'
			if len(str(arr)) == 2:
				arr = '00' + str(arr)
			if len(str(arr)) == 1:
				arr = '000' + str(arr)
			c = 2
			if len(str(arr)) == 3:
				c -= 1
			return int(str(arr)[:c]) * 60 + int(str(arr)[c:])
		time = []
		for (a, d) in zip(arr, dep):
			a = conv(a)
			d = conv(d)
			time.append((a, d))
		time.sort(key=lambda x: (x[0], x[1] - x[0]))
		heap = []
		c = 0
		for (a, d) in time:
			if not heap:
				c += 1
				heapq.heappush(heap, d)
			else:
				val = heapq.heappop(heap)
				if val < a:
					heapq.heappush(heap, d)
				else:
					c += 1
					heapq.heappush(heap, d)
					heapq.heappush(heap, val)
		return c


class Solution:

	def minimumPlatform(self, n, arr, dep):
		train = []
		for i in range(n):
			train.append([arr[i], 'a'])
			train.append([dep[i], 'd'])
		train = sorted(train)
		n = len(train)
		count = 0
		a = 0
		d = 0
		for i in train:
			if i[1] == 'a':
				a += 1
			else:
				d += 1
			count = max(count, abs(a - d))
		return count


class Solution:

	def func(self, a, b):
		if a[1] < b[1] or a[2] < b[2]:
			return a
		return b

	def minimumPlatform(self, n, arr, dep):
		train = []
		for i in range(n):
			train.append([arr[i], 'a'])
			train.append([dep[i], 'd'])
		train = sorted(train, key=lambda x: x[1])
		train = sorted(train, key=lambda x: x[0])
		n = len(train)
		count = 0
		a = 0
		d = 0
		for i in train:
			if i[1] == 'a':
				a += 1
			else:
				d += 1
			count = max(count, abs(a - d))
		return count


from bisect import bisect_left, bisect_right
from collections import defaultdict

class Solution:

	def minimumPlatform(self, n, arr, dep):
		platforms = defaultdict(int)
		for a in arr:
			platforms[a] += 1
		for d in dep:
			platforms[d + 1] -= 1
		r = 1
		cumsum = 0
		for k in sorted(platforms.keys()):
			cumsum += platforms[k]
			r = max(cumsum, r)
		return r


class Solution:

	def TimeInMinutes(self, time):
		if time >= 0 and time <= 2359:
			return time // 100 * 60 + time % 100
		else:
			print('Invalid time input:', time)
			return 0

	def minimumPlatform(self, n, arr, dep):
		MaxPlatform = 0
		platReq = {}
		for t in range(n):
			m_arr = self.TimeInMinutes(arr[t])
			m_dep = self.TimeInMinutes(dep[t])
			sValue = platReq.get(m_arr, 0)
			eValue = platReq.get(m_dep, 0)
			if sValue == 0:
				platReq[m_arr] = 'S'
			else:
				platReq[m_arr] = sValue + 'S'
			if eValue == 0:
				platReq[m_dep] = 'E'
			else:
				platReq[m_dep] = eValue + 'E'
		newPlat = sorted(platReq.items())
		MaxV = 0
		count = 0
		for i in range(len(newPlat)):
			v = newPlat[i][1]
			count += v.count('S')
			MaxV = max(count, MaxV)
			count -= v.count('E')
		return MaxV


class Solution:

	def minimumPlatform(self, n, arr, dep):
		maxi = 0
		c = 0
		arr.sort()
		dep.sort()
		(i, j) = (0, 0)
		while i < n:
			if arr[i] <= dep[j]:
				c += 1
				maxi = max(maxi, c)
				i += 1
			else:
				c -= 1
				j += 1
		return maxi


class Solution:

	def minimumPlatform(self, n, arr, dep):
		cnt = 1
		m = 0
		arr.sort()
		dep.sort()
		(i, j) = (1, 0)
		while i < n:
			if arr[i] <= dep[j]:
				cnt = cnt + 1
				i = i + 1
				m = max(cnt, m)
			else:
				j = j + 1
				cnt = cnt - 1
		return m


class Solution:

	def minimumPlatform(self, n, arr, dep):
		temp = []
		for el in dep:
			temp.append([el, 'd'])
		for el in arr:
			temp.append([el, 'a'])
		temp.sort()
		m = 0
		cnt = 0
		for el in temp:
			if el[1] == 'a':
				cnt = cnt + 1
				m = max(m, cnt)
			else:
				cnt = cnt - 1
		return m


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		i = j = 0
		platforms = 0
		current_platforms = 0
		while i < n and j < n:
			if arr[i] <= dep[j]:
				current_platforms += 1
				i += 1
			else:
				current_platforms -= 1
				j += 1
			platforms = max(platforms, current_platforms)
		return platforms


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arrival.sort()
		departure.sort()
		platform_needed = 1
		result = 1
		i = 1
		j = 0
		n = len(arrival)
		while i < n and j < n:
			if arrival[i] <= departure[j]:
				platform_needed += 1
				i += 1
				if platform_needed > result:
					result = platform_needed
			else:
				platform_needed -= 1
				j += 1
		return result


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		(m, p, j) = (0, 1, 0)
		for i in range(1, n):
			while j < i and dep[j] < arr[i]:
				j += 1
			p = i - j + 1
			m = max(m, p)
		return m


class Solution:

	def minimumPlatform(self, n, arr, dep):
		l = [0] * 2400
		for i in arr:
			l[i] += 1
		for i in dep:
			l[i + 1] -= 1
		p = 0
		for i in range(1, 2400):
			l[i] += l[i - 1]
			p = max(p, l[i])
		return p


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		i = 1
		j = 0
		minPlatformsReqd = 1
		currentPlatformsUsed = 1
		while i < n and j < n:
			if int(dep[j]) >= int(arr[i]):
				i += 1
				currentPlatformsUsed += 1
				minPlatformsReqd = max(minPlatformsReqd, currentPlatformsUsed)
			else:
				j += 1
				currentPlatformsUsed -= 1
		return minPlatformsReqd


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		platform = 1
		i = 1
		j = 0
		temp = 1
		while i < n and j < n:
			if int(dep[j]) >= int(arr[i]):
				i = i + 1
				temp = temp + 1
				platform = max(platform, temp)
			else:
				j = j + 1
				temp = temp - 1
		return platform


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		i = 0
		ans = 1
		for j in range(1, n):
			if arr[j] <= dep[i]:
				ans += 1
			else:
				i += 1
		return ans


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		platforms = 1
		max_platforms = 1
		(i, j) = (1, 0)
		while i < n and j < n:
			if arr[i] <= dep[j]:
				platforms += 1
				i += 1
			elif arr[i] > dep[j]:
				platforms -= 1
				j += 1
			if platforms > max_platforms:
				max_platforms = platforms
		return max_platforms


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		n = len(arr)
		platforms = 1
		max_platforms = 1
		(arr_idx, dep_idx) = (1, 0)
		while arr_idx < n and dep_idx < n:
			if arr[arr_idx] <= dep[dep_idx]:
				platforms += 1
				arr_idx += 1
			else:
				platforms -= 1
				dep_idx += 1
			max_platforms = max(max_platforms, platforms)
		return max_platforms


import heapq as pq

class Solution:

	def minimumPlatform(self, n, arr, dep):
		lst = []
		for i in range(n):
			lst.append([arr[i], dep[i]])

		def myfunc(e):
			return e[0]
		lst.sort(key=myfunc)
		ans = 1
		end_lst = []
		pq.heappush(end_lst, lst[0][1])
		for i in range(1, n):
			num = end_lst[0]
			if lst[i][0] > num:
				pq.heappop(end_lst)
				pq.heappush(end_lst, lst[i][1])
				pq.heapify(end_lst)
			else:
				ans += 1
				pq.heappush(end_lst, lst[i][1])
				pq.heapify(end_lst)
		return ans


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		dp = []
		count = 0
		for i in range(0, n):
			if i == 0:
				count += 1
				dp.append(dep[0])
			else:
				j = min(dp)
				if j < arr[i]:
					dp[dp.index(j)] = dep[i]
					j = min(dp)
				else:
					dp.append(dep[i])
					count += 1
		return count


class Solution:

	def minimumPlatform(self, n, arr, dep):
		d = {}
		for i in range(n):
			if arr[i] in d:
				if type(d[arr[i]]) == str:
					d[arr[i]] = ['a', 'a']
				else:
					d[arr[i]].append('a')
			else:
				d[arr[i]] = 'a'
		for i in range(n):
			if dep[i] in d:
				if type(d[dep[i]]) == str:
					d[dep[i]] = [d[dep[i]], 'd']
				else:
					d[dep[i]].append('d')
			else:
				d[dep[i]] = 'd'
		keys_sort = sorted(d)
		c = 0
		max_count = 0
		for key in keys_sort:
			if type(d[key]) == str:
				if d[key] == 'a':
					c += 1
					if max_count < c:
						max_count = c
				else:
					c -= 1
			else:
				for i in d[key]:
					if i == 'a':
						c += 1
						if max_count < c:
							max_count = c
					else:
						c -= 1
		return max_count


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		plat = 1
		max_p = 1
		(i, j) = (1, 0)
		while i < n and j < n:
			if arr[i] <= dep[j]:
				plat += 1
				i += 1
			else:
				plat -= 1
				j += 1
			if plat >= max_p:
				max_p = plat
		return max_p


class Solution:

	def minimumPlatform(self, n, arr, dep):
		schedule = [(arrival, departure) for (arrival, departure) in zip(arr, dep)]
		schedule.sort()
		prev_departures = [float('-inf')]
		for (arrival, departure) in schedule:
			for (i, prev_departure) in enumerate(prev_departures):
				if prev_departure < arrival:
					prev_departures[i] = departure
					break
			else:
				prev_departures.append(departure)
		return len(prev_departures)


import heapq

class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		ans = 0
		cur = 0
		(i, j) = (0, 0)
		while i < len(arr) and j < len(dep):
			if arr[i] <= dep[j]:
				cur += 1
				i += 1
				ans = max(ans, cur)
			else:
				cur -= 1
				j += 1
		return ans


import heapq

class Solution:

	def minimumPlatform(self, n, arr, dep):
		nums = []
		for i in range(n):
			nums.append([arr[i], dep[i]])
		nums.sort(key=lambda x: x[0])
		pq = []
		heapq.heappush(pq, nums[0][1])
		ans = 1
		for i in range(1, len(nums)):
			if pq and pq[0] < nums[i][0]:
				heapq.heappop(pq)
				heapq.heappush(pq, nums[i][1])
			else:
				ans += 1
				heapq.heappush(pq, nums[i][1])
		return ans


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		a = [dep[0]]
		p = 1
		for i in range(1, n):
			k = 0
			for j in range(len(a)):
				if a[j] < arr[i]:
					a.pop(j)
					a.append(dep[i])
					k = 1
					break
			if k == 0:
				p += 1
				a.append(dep[i])
		return p


import heapq

class Solution:

	def minimumPlatform(self, n, arr, dep):
		trains = []
		for i in range(n):
			trains.append((arr[i], dep[i]))
		trains.sort(key=lambda x: x[0])
		platforms = [trains[0][1]]
		i = 1
		while i < n:
			(a_t, d_t) = (trains[i][0], trains[i][1])
			if a_t <= platforms[0]:
				heapq.heappush(platforms, d_t)
			else:
				heapq.heappop(platforms)
				heapq.heappush(platforms, d_t)
			i += 1
		return len(platforms)


class Solution:

	def minimumPlatform(self, n, arr, dep):
		max_platforms = 0
		arr.sort()
		dep.sort()
		a = 0
		d = 0
		i_platforms = 0
		while a < n and d < n:
			if arr[a] <= dep[d]:
				i_platforms += 1
				a += 1
				max_platforms = max(max_platforms, i_platforms)
			else:
				i_platforms -= 1
				d += 1
		return max_platforms


class Solution:

	def minimumPlatform(self, n, arrival, departure):
		arrival.sort()
		departure.sort()
		platforms = 1
		max_platforms = 1
		i = 1
		j = 0
		while i < len(arrival) and j < len(departure):
			if arrival[i] <= departure[j]:
				platforms += 1
				i += 1
				if platforms > max_platforms:
					max_platforms = platforms
			else:
				platforms -= 1
				j += 1
		return max_platforms


class Solution:

	def minimumPlatform(self, n, arr, dep):
		c = 1
		arr.sort()
		dep.sort()
		platforms_needed_at_a_time = 0
		result = 0
		i = 0
		j = 0
		while i < n and j < n:
			if arr[i] <= dep[j]:
				platforms_needed_at_a_time += 1
				i += 1
			elif dep[j] < arr[i]:
				platforms_needed_at_a_time -= 1
				j += 1
			result = max(platforms_needed_at_a_time, result)
		return result


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		i = j = count = max1 = 0
		while i < n:
			if arr[i] <= dep[j]:
				i += 1
				count += 1
				max1 = max(max1, count)
			else:
				j += 1
				count -= 1
		return max1


class Solution:

	def minimumPlatform(self, n, arr, dep):
		plat_needed = 1
		final_count = 1
		arr.sort()
		dep.sort()
		(i, j) = (1, 0)
		while i < n and j < n:
			if arr[i] <= dep[j]:
				plat_needed += 1
				i += 1
			else:
				plat_needed -= 1
				j += 1
			if plat_needed > final_count:
				final_count = plat_needed
		return final_count


class Solution:

	def minimumPlatform(self, n, arr, dep):
		count = 0
		plat = []
		max_count = 0
		for i in arr:
			plat.append((i, 'a'))
		for i in dep:
			plat.append((i, 'd'))
		plat_1 = sorted(plat, key=lambda tup: tup[0])
		for i in plat_1:
			if i[1] == 'a':
				count += 1
			else:
				count -= 1
			max_count = max(count, max_count)
		return max_count


class Solution:

	def minimumPlatform(self, n, arr, dep):

		def findPlatform(arr, dep, n):
			times = []
			for i in range(n):
				times.append([dep[i], 'd'])
				times.append([arr[i], 'a'])
			times = sorted(times, key=lambda x: x[1])
			times = sorted(times, key=lambda x: x[0])
			(result, plat_needed) = (0, 0)
			for i in range(2 * n):
				if times[i][1] == 'a':
					plat_needed += 1
					result = max(plat_needed, result)
				else:
					plat_needed -= 1
			return result
		return findPlatform(arr, dep, n)
arr = [900, 940, 950, 1100, 1500, 1800]
dep = [910, 1200, 1120, 1130, 1900, 2000]
n = len(arr)


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		i = 1
		j = 0
		ans = 1
		platform = 1
		while i < n and j < n:
			if arr[i] <= dep[j]:
				platform += 1
				i += 1
			elif arr[i] > dep[j]:
				platform -= 1
				j += 1
			if platform > ans:
				ans = platform
		return ans


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr = sorted(arr)
		dep = sorted(dep)
		nplatform = 0
		while len(arr) > 0:
			nplatform = nplatform + 1
			ia = 0
			id = ia * 1
			chain = [0]
			dep_val = dep[0]
			del arr[0]
			del dep[0]
			nremaining = len(arr)
			for j in range(nremaining):
				if dep_val < arr[ia]:
					dep_val = dep[ia]
					del arr[ia]
					del dep[ia]
					id = ia * 1
				else:
					ia = ia + 1
					pass
		return nplatform


class Solution:

	def minimumPlatform(self, n, arr, dep):
		i = 0
		j = 0
		arr.sort()
		dep.sort()
		p = 0
		m = p
		while i < len(arr) and j < len(dep):
			if arr[i] <= dep[j]:
				p += 1
				i += 1
			else:
				p -= 1
				j += 1
			m = max(m, p)
		return m


import heapq

class Solution:

	def minimumPlatform(self, n, arr, dep):
		trains = [(arr[i], dep[i]) for i in range(n)]
		trains.sort(key=lambda x: x[0])
		min_heap = []
		heapq.heappush(min_heap, trains[0][1])
		cnt = 1
		for i in range(1, n):
			if trains[i][0] <= min_heap[0]:
				cnt += 1
			else:
				heapq.heappop(min_heap)
			heapq.heappush(min_heap, trains[i][1])
		return cnt


class Solution:

	def minimumPlatform(self, n, arr, dep):
		arr.sort()
		dep.sort()
		platforms = 0
		maxx = 0
		i = 0
		j = 0
		while i < n:
			a = arr[i]
			d = dep[j]
			if a <= d:
				platforms += 1
				i += 1
			else:
				platforms -= 1
				j += 1
			maxx = max(maxx, platforms)
		return maxx


class Solution:

	def minimumPlatform(self, n, arr, dep):
		dic = {}
		for i in range(n):
			if arr[i] in dic:
				dic[arr[i]] += 1
			else:
				dic[arr[i]] = 1
			if dep[i] + 1 in dic:
				dic[dep[i] + 1] -= 1
			else:
				dic[dep[i] + 1] = -1
		ans = 0
		cnt = 0
		for el in sorted(dic):
			cnt += dic[el]
			ans = max(ans, cnt)
		return ans