Given N intervals of the form [A, B]. The task is to return the maximum number of overlap among these intervals at any time.
Example 1:
Input:
N = 3
Intervals[] = {{1, 2}, {2, 4}, {3, 6}}
Output: 
2
Explanation: 
The maximum overlapping is 2(between (1 2) and 
(2 4) or between (2 4) and (3 6)) 
Example 2:
Input:
N = 4
Intervals[] = {{1, 8}, {2, 5}, {5, 6}, {3, 7}}
Output: 
4
Explanation: 
The maximum overlapping is 4 (between (1, 8), 
(2, 5), (5, 6) and (3, 7))
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function overlap() which takes a list of pairs as input and returns an integer as output.
 
Expected Time Complexity: O(N * log N)
Expected Auxiliary Space: O(N)
 
Constraints:
2 <= N <= 2 * 10^{4}
1<= intervals[i][0] < intervals[i][1] <= 4*10^{3}

Difficulty: MEDIUM_HARD
Expected Time Complexity: O(N * log N)
Expected Auxiliary Space: O(N)

Starter code:


from typing import List





class Solution:

    def overlap(self, n : int, intervals : List[List[int]]) -> int:

        # code here

        



Solutions:
from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		beginnings = sorted([i[0] for i in intervals])
		endings = sorted([i[1] for i in intervals])
		answer = -1
		temp = []
		for i in range(len(beginnings)):
			val = beginnings[i]
			temp.append(val)
			while endings[0] < val:
				temp.pop(0)
				endings.pop(0)
			answer = max(answer, len(temp))
		return answer


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		(ans, count) = (0, 0)
		l = []
		for i in intervals:
			l.append([i[0], 'x'])
			l.append([i[1], 'y'])
		l.sort()
		for i in l:
			if i[1] == 'x':
				count += 1
			else:
				count -= 1
			ans = max(ans, count)
		return ans


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		(start_intervals, end_intervals) = zip(*intervals)
		start_intervals = sorted(list(start_intervals))
		end_intervals = sorted(list(end_intervals))
		start_interval_iterator = 0
		end_interval_iterator = 0
		sim_meetings = 0
		max_meetings = 0
		while end_interval_iterator < n:
			if start_interval_iterator >= n or start_intervals[start_interval_iterator] > end_intervals[end_interval_iterator]:
				sim_meetings -= 1
				end_interval_iterator += 1
			else:
				sim_meetings += 1
				start_interval_iterator += 1
			if sim_meetings > max_meetings:
				max_meetings = sim_meetings
		return max_meetings


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		s = sorted([s for (s, e) in intervals])
		e = sorted([e for (s, e) in intervals])
		(i, j) = (0, 0)
		curr = 0
		ans = 0
		while i < n and j < n:
			if s[i] <= e[j]:
				curr += 1
				i += 1
			else:
				curr -= 1
				j += 1
			ans = max(ans, curr)
		return ans


from typing import List

class Solution:

	def overlap(self, n: int, v: List[List[int]]) -> int:
		ans = 0
		count = 0
		data = []
		for i in range(len(v)):
			data.append([v[i][0], 'x'])
			data.append([v[i][1], 'y'])
		data = sorted(data)
		for i in range(len(data)):
			if data[i][1] == 'x':
				count += 1
			if data[i][1] == 'y':
				count -= 1
			ans = max(ans, count)
		return ans


from typing import List
import collections

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		endpoints = []
		Endpoint = collections.namedtuple('Endpoint', ('val', 'is_start'))
		for interval in intervals:
			u1 = Endpoint(interval[0], True)
			u2 = Endpoint(interval[1], False)
			endpoints.append(u1)
			endpoints.append(u2)
		endpoints.sort(key=lambda x: (x.val, not x.is_start))
		count = 0
		ans = 0
		for e in endpoints:
			if e.is_start:
				count += 1
				ans = max(ans, count)
			else:
				count -= 1
		return ans


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		l = []
		for i in intervals:
			l.append([i[0], 0])
			l.append([i[1], 1])
		l.sort()
		c = 0
		m = 0
		for i in l:
			if i[1] == 0:
				c += 1
			else:
				c -= 1
			m = max(m, c)
		return m


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		tem = []
		for (u, v) in intervals:
			tem.append([u, 'x'])
			tem.append([v, 'y'])
		tem.sort()
		counti = 0
		maxi = 0
		for (u, v) in tem:
			if v == 'x':
				counti += 1
				maxi = max(maxi, counti)
			else:
				counti -= 1
		return maxi


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		arr1 = [intervals[i][0] for i in range(len(intervals))]
		arr2 = [intervals[i][1] for i in range(len(intervals))]
		arr1.sort()
		arr2.sort()
		res = 0
		count = 0
		i = 0
		j = 0
		while i < len(arr1) and j < len(arr2):
			if arr1[i] <= arr2[j]:
				count += 1
				res = max(res, count)
				i += 1
			else:
				count -= 1
				j += 1
		return res


from typing import List

class Solution:

	def overlap(self, n: int, iv: List[List[int]]) -> int:
		d = []
		for (s, e) in iv:
			d.append((s, 'x'))
			d.append((e, 'y'))
		count = 0
		ans = 0
		d = sorted(d)
		for (_, k) in d:
			if k == 'x':
				ans += 1
			else:
				ans -= 1
			count = max(count, ans)
		return count


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		ans = 0
		count = 0
		data = []
		for i in range(len(intervals)):
			data.append([intervals[i][0], 'x'])
			data.append([intervals[i][1], 'y'])
		data.sort()
		for i in range(len(data)):
			if data[i][1] == 'x':
				count += 1
			elif data[i][1] == 'y':
				count -= 1
			ans = max(ans, count)
		return ans


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		v = []
		for (s, e) in intervals:
			v.append((s, 1))
			v.append((e, 2))
		v.sort()
		maxx = 0
		count = 0
		for (t, i) in v:
			if i == 1:
				count += 1
			else:
				count -= 1
			maxx = max(maxx, count)
		return maxx


from typing import List
from itertools import accumulate

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		r = [0] * (max(map(lambda x: x[1], intervals)) + 2)
		for (l, h) in intervals:
			r[l] += 1
			r[h + 1] -= 1
		return max(accumulate(r))

class IntMatrix:

	def __init__(self) -> None:
		pass

	def Input(self, n, m):
		matrix = []
		for _ in range(n):
			matrix.append([int(i) for i in input().strip().split()])
		return matrix

	def Print(self, arr):
		for i in arr:
			for j in i:
				print(j, end=' ')
			print()
if __name__ == '__main__':
	t = int(input())
	for _ in range(t):
		n = int(input())
		intervals = IntMatrix().Input(n, n)
		obj = Solution()
		res = obj.overlap(n, intervals)
		print(res)


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		(start_time, end_time) = ([], [])
		for (s, e) in intervals:
			start_time.append(s)
			end_time.append(e)
		start_time.sort()
		end_time.sort()
		(start, end, count, res) = (0, 0, 0, 0)
		while start < len(intervals):
			if start_time[start] <= end_time[end]:
				count += 1
				start += 1
			else:
				count -= 1
				end += 1
			res = max(res, count)
		return res


from typing import List

class Solution:

	def overlap(self, n: int, int: List[List[int]]) -> int:
		l = [0 for i in range(2 * 10 ** 4 + 2)]
		for i in range(n):
			l[int[i][0]] += 1
			l[int[i][1] + 1] -= 1
		for i in range(1, 2 * 10 ** 4 + 2):
			l[i] += l[i - 1]
		return max(l)


from typing import List

class Solution:

	def overlap(self, n: int, intervals: List[List[int]]) -> int:
		ans = []
		for val in intervals:
			ans.append((val[0], 'x'))
			ans.append((val[1], 'y'))
		ans.sort()
		ans1 = 0
		c = 0
		for val in ans:
			if val[1] == 'x':
				c += 1
			else:
				c -= 1
			ans1 = max(ans1, c)
		return ans1


from typing import List
from heapq import heappush, heappop

class Solution:

	def overlap(self, n: int, inter: List[List[int]]) -> int:
		inter.sort()
		h = [inter[0][1]]
		over = 1
		for i in range(1, n):
			if inter[i][0] <= h[0]:
				over += 1
			else:
				heappop(h)
			heappush(h, inter[i][1])
		return over