N horizontal line segments are arranged on the X-axis of a 2D plane. The start and end point of each line segment is given in a Nx2 matrix lines[ ][ ]. Your task is to find the maximum number of intersections possible of any vertical line with the given N line segments.
Example 1:
Input:
N = 4
lines[][] = {{1,3}, {2,3}, {1,2}, {4,4}}
Output:
3
Explanation:
A vertical line at X = 2 passes through 
{1,3}, {2,3}, {1,2}, ie three of the 
given horizontal lines.
Example 2:
Input: 
N = 3
lines[][] = {{1, 3}, {5, 6}, {3,4}}
Output:
2
Explanation: 
A vertical line at X = 3 passes through 
two of the given horizontal lines which 
is the maximum possible.
Your Task:
You dont need to read input or print anything. Complete the function maxIntersections() which takes the 2D Matrix lines[][] and the integer N as input parameters, and returns the maximum intersections possible.
Expected Time Complexity: O(N*log(N))
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5 }
-10^{9 }≤ lines[i][0] ≤ 10^{9}
lines[i][0] ≤ lines[i][1] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Geometry

Sorting

Mathematics

Starter code: #User function Template for python3



class Solution: 

    def maxIntersections(self, lines, N):

        # Code here

Solutions:
class Solution:

	def maxIntersections(self, lines, N):
		l1 = []
		l2 = []
		for p in lines:
			l1.append(p[0])
			l2.append(p[1])
		l1.sort()
		l2.sort()
		i = 0
		j = 0
		ans = 0
		k = 0
		while i < N and j < N:
			if l1[i] <= l2[j]:
				k += 1
				ans = max(ans, k)
				i += 1
			else:
				k -= 1
				j += 1
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		list = []
		kist = []
		for a in lines:
			list.append(a[0])
			kist.append(a[1])
		list.sort()
		kist.sort()
		(i, j, ans, k) = (0, 0, 0, 0)
		while i < N and j < N:
			if list[i] <= kist[j]:
				k += 1
				ans = max(ans, k)
				i += 1
			else:
				k -= 1
				j += 1
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		a = {}
		for i in range(N):
			a[lines[i][0]] = a.get(lines[i][0], 0) + 1
			a[lines[i][1] + 1] = a.get(lines[i][1] + 1, 0) - 1
		ans = 0
		s = 0
		for i in sorted(a):
			s += a[i]
			ans = max(ans, s)
		return ans


class Solution:

	def maxIntersections(self, lines, n):
		(start, end) = ([], [])
		for l in lines:
			start.append(l[0])
			end.append(l[1])
		start.sort()
		end.sort()
		(i, j) = (0, 0)
		ans = 0
		intersection = 0
		while i < n and j < n:
			if start[i] <= end[j]:
				intersection += 1
				ans = max(ans, intersection)
				i += 1
			else:
				intersection -= 1
				j += 1
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		lineMap = dict()
		for line in lines:
			start = line[0]
			end = line[1] + 1
			if start in lineMap:
				lineMap[start] += 1
			else:
				lineMap[start] = 1
			if end in lineMap:
				lineMap[end] -= 1
			else:
				lineMap[end] = -1
		res = 0
		cnt = 0
		for entry in sorted(lineMap.keys()):
			cnt += lineMap[entry]
			res = max(res, cnt)
		return res


from sortedcontainers import SortedDict

class Solution:

	def maxIntersections(self, arr, N):
		mp = {}
		for x in arr:
			s = x[0]
			e = x[1] + 1
			mp[s] = mp.get(s, 0) + 1
			mp[e] = mp.get(e, 0) - 1
		mmax = 0
		presum = 0
		mp = SortedDict(mp)
		for x in mp:
			presum += mp[x]
			mmax = max(mmax, presum)
		return mmax


from sortedcontainers import SortedDict

class Solution:

	def maxIntersections(self, lines, N):
		d = {}
		for (i, j) in lines:
			d[i] = d.get(i, 0) + 1
			d[j + 1] = d.get(j + 1, 0) - 1
		ans = 0
		res = 0
		d = SortedDict(d)
		for i in d:
			ans += d[i]
			res = max(res, ans)
		return res


class Solution:

	def maxIntersections(self, lines, N):
		(start_lines, end_lines) = zip(*lines)
		start_lines = sorted(start_lines)
		end_lines = sorted(end_lines)
		curr_intersect = 0
		max_intersect = 0
		(i, j) = (0, 0)
		while i < N:
			if start_lines[i] <= end_lines[j]:
				curr_intersect += 1
				max_intersect = max(max_intersect, curr_intersect)
				i += 1
			else:
				curr_intersect -= 1
				j += 1
		return max_intersect


class Solution:

	def maxIntersections(self, lines, N):
		from collections import defaultdict
		dct = defaultdict(int)
		curr_intersect = 0
		max_intersect = 0
		for (start, end) in lines:
			dct[start] += 1
			dct[end + 1] -= 1
		for key in sorted(dct):
			curr_intersect += dct[key]
			max_intersect = max(max_intersect, curr_intersect)
		return max_intersect


from collections import *

class Solution:

	def maxIntersections(self, lines, n):
		d = defaultdict(int)
		for (a, b) in lines:
			d[a] += 1
			d[b + 1] -= 1
		cur = 0
		ans = 0
		lis = sorted(d.keys())
		for i in lis:
			cur += d[i]
			ans = max(ans, cur)
		return ans


from collections import defaultdict

class Solution:

	def maxIntersections(self, lines, N):
		dp = defaultdict(int)
		for (i, j) in lines:
			dp[i] += 1
			dp[j + 1] -= 1
		ans = 0
		presum = 0
		dp2 = sorted(dp.keys())
		for ele in dp2:
			presum = dp[ele] + presum
			ans = max(ans, presum)
		return ans


class Solution:

	def maxIntersections(self, a, N):
		d = {}
		for i in a:
			if i[0] in d:
				d[i[0]] += 1
			else:
				d[i[0]] = 1
			if i[1] + 1 in d:
				d[i[1] + 1] -= 1
			else:
				d[i[1] + 1] = -1
		l = sorted(d)
		(smallest_res, res) = (1, 0)
		for i in l:
			res += d[i]
			smallest_res = max(smallest_res, res)
		return smallest_res


class Solution:

	def maxIntersections(self, lines, N):
		dic = {}
		for i in range(N):
			if lines[i][0] in dic:
				dic[lines[i][0]] += 1
			else:
				dic[lines[i][0]] = 1
			if lines[i][1] + 1 in dic:
				dic[lines[i][1] + 1] -= 1
			else:
				dic[lines[i][1] + 1] = -1
		a = min(dic)
		b = max(dic)
		res = 0
		mx = -99999999
		for i in sorted(dic):
			res += dic[i]
			mx = max(res, mx)
		return mx


from sortedcontainers import SortedDict

class Solution:

	def maxIntersections(self, lines, N):
		dic = {}
		for i in lines:
			k = i[0]
			p = i[1] + 1
			dic[k] = dic.get(k, 0) + 1
			dic[p] = dic.get(p, 0) - 1
		m = 0
		s = 0
		dic = SortedDict(dic)
		for i in dic:
			s += dic[i]
			m = max(m, s)
		return m


import sys
from collections import defaultdict

class Solution:

	def maxIntersections(self, lines, N):
		d = defaultdict(int)
		mini = sys.maxsize
		maxi = -sys.maxsize
		for i in lines:
			(a, b) = i
			d[a] += 1
			d[b + 1] -= 1
			mini = min(mini, a)
			maxi = max(maxi, b)
		ans = -1
		count = 0
		for i in sorted(d.keys()):
			count += d[i]
			ans = max(ans, count)
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		d = {}
		for i in lines:
			d[i[0]] = d.get(i[0], 0) + 1
			d[i[1] + 1] = d.get(i[1] + 1, 0) - 1
		p = 0
		maxi = 1
		for i in sorted(d):
			p += d[i]
			maxi = max(maxi, p)
		return maxi


class Solution:

	def maxIntersections(self, lines, N):
		endpoints = []
		for line in lines:
			endpoints.append((line[0], 'l'))
			endpoints.append((line[1], 'r'))
		endpoints.sort()
		count = 0
		for i in range(len(endpoints)):
			if endpoints[i][1] == 'r':
				count += 1
			elif count > 0:
				count -= 1
		return count


from sortedcontainers import SortedDict

class Solution:

	def maxIntersections(self, lines, N):
		start = []
		end = []
		for a in lines:
			start.append(a[0])
			end.append(a[1])
		start.sort()
		end.sort()
		(i, j, ans, k) = (0, 0, 0, 0)
		while i < N and j < N:
			if start[i] <= end[j]:
				k += 1
				ans = max(ans, k)
				i += 1
			else:
				k -= 1
				j += 1
		return ans


import math

class Solution:

	def maxIntersections(self, lines, N):
		sp = []
		ep = []
		for (i, j) in lines:
			sp.append(i)
			ep.append(j)
		sp.sort()
		ep.sort()
		inter = 0
		i = 0
		j = 0
		ans = -math.inf
		while i < N and j < N:
			if sp[i] <= ep[j]:
				inter += 1
				ans = max(ans, inter)
				i += 1
			else:
				inter -= 1
				j += 1
		return ans


from heapq import heapify, heappop, heappush

class Solution:

	def maxIntersections(self, lines, N):
		lines.sort()
		ans = 0
		pq = []
		heapify(pq)
		cur = 0
		ans = 0
		for (l, r) in lines:
			while pq and pq[0] < l:
				cur -= 1
				heappop(pq)
			cur += 1
			heappush(pq, r)
			ans = max(ans, cur)
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		m = {}
		for l in lines:
			l1 = l[0]
			l2 = l[1]
			if l1 in m:
				m[l1] += 1
			else:
				m[l1] = 1
			if l2 + 1 in m:
				m[l2 + 1] -= 1
			else:
				m[l2 + 1] = -1
		ans = 0
		s = 0
		for i in sorted(m):
			s += m[i]
			ans = max(ans, s)
		return ans


class Solution:

	def maxIntersections(self, arr, N):
		mem = {}
		for (st, end) in arr:
			mem[st] = mem.get(st, 0) + 1
			mem[end + 1] = mem.get(end + 1, 0) - 1
		res = cur = 0
		for i in sorted(mem.keys()):
			cur += mem[i]
			res = max(res, cur)
		return res


class Solution:

	def maxIntersections(self, lines, n):
		arr1 = []
		arr2 = []
		for i in lines:
			arr1.append(i[0])
			arr2.append(i[1])
		arr1.sort()
		arr2.sort()
		ans = 0
		p = 0
		i = 0
		j = 0
		while i < n and j < n:
			if arr1[i] <= arr2[j]:
				p += 1
				i += 1
			else:
				p -= 1
				j += 1
			ans = max(ans, p)
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		s = []
		e = []
		for (st, en) in lines:
			s.append(st)
			e.append(en)
		s.sort()
		e.sort()
		(i, j) = (0, 0)
		(l, ans) = (0, 0)
		while i < len(s) and j < len(e):
			if s[i] <= e[j]:
				l += 1
				ans = max(ans, l)
				i += 1
			else:
				j += 1
				l -= 1
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		x = []
		y = []
		for i in range(N):
			x.append(lines[i][0])
			y.append(lines[i][1])
		x.sort()
		y.sort()
		i = 0
		j = 0
		ans = 0
		count = 0
		while i < N and j < N:
			if x[i] <= y[j]:
				count += 1
				i += 1
			else:
				count -= 1
				j += 1
			ans = max(ans, count)
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		dic = {}
		for i in lines:
			if i[0] in dic:
				dic[i[0]] += 1
			else:
				dic[i[0]] = 1
			if i[1] + 1 in dic:
				dic[i[1] + 1] -= 1
			else:
				dic[i[1] + 1] = -1
		cnt = 0
		ma = float('-inf')
		for i in sorted(dic.keys()):
			cnt += dic[i]
			ma = max(ma, cnt)
		return ma


import math

class Solution:

	def maxIntersections(self, lines, N):
		start = []
		end = []
		for i in lines:
			start.append(i[0])
			end.append(i[1])
		start.sort()
		end.sort()
		i = 0
		j = 0
		ans = 0
		m = -math.inf
		while i < N and j < N:
			if start[i] <= end[j]:
				ans += 1
				m = max(m, ans)
				i += 1
			else:
				ans -= 1
				j += 1
		return m


from typing import List

class Solution:

	@staticmethod
	def maxIntersections(l: List[List[int]], n: int) -> int:
		m = {}
		for i in range(n):
			if l[i][0] not in m:
				m[l[i][0]] = 1
			else:
				m[l[i][0]] += 1
			if l[i][1] + 1 not in m:
				m[l[i][1] + 1] = -1
			else:
				m[l[i][1] + 1] -= 1
		(c, pre_sum) = (0, 0)
		for x in sorted(m):
			pre_sum += m[x]
			c = max(c, pre_sum)
		return c


class Solution:

	def maxIntersections(self, lines, N):
		o = {}
		for i in lines:
			o[i[0]] = o.get(i[0], 0) + 1
			o[i[1] + 1] = o.get(i[1] + 1, 0) - 1
		p = 0
		m = 1
		for i in sorted(o):
			p = p + o[i]
			m = max(m, p)
		return m


class Solution:

	def maxIntersections(self, lines, N):
		d = {}
		for (i, j) in lines:
			if i not in d:
				d[i] = 1
			else:
				d[i] += 1
			if j + 1 not in d:
				d[j + 1] = -1
			else:
				d[j + 1] -= 1
		k = sorted(d.items(), key=lambda x: x[0])
		count = 0
		m = 0
		for (i, j) in k:
			count += j
			m = max(m, count)
		return m


class Solution:

	def maxIntersections(self, lines, N):
		slines = []
		elines = []
		for point in lines:
			slines.append(point[0])
			elines.append(point[1])
		slines.sort()
		elines.sort()
		i = 0
		j = 0
		ans = -1000000000.0
		intersections = 0
		while i < N and j < N:
			if slines[i] <= elines[j]:
				intersections += 1
				ans = max(ans, intersections)
				i += 1
			else:
				intersections -= 1
				j += 1
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		lst = []
		kst = []
		for i in lines:
			lst.append(i[0])
			kst.append(i[1])
		lst.sort()
		kst.sort()
		(i, j, ans, k) = (0, 0, 0, 0)
		while i < N and j < N:
			if lst[i] <= kst[j]:
				k += 1
				ans = max(ans, k)
				i += 1
			else:
				k -= 1
				j += 1
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		first = []
		second = []
		for i in range(N):
			first.append(lines[i][0])
			second.append(lines[i][1])
		first.sort()
		second.sort()
		i = 0
		j = 0
		mx = -2147483648
		intersection = 0
		while i < N and j < N:
			if first[i] <= second[j]:
				i += 1
				intersection += 1
				mx = max(intersection, mx)
			else:
				j += 1
				intersection -= 1
		return mx


class Solution:

	def maxIntersections(self, lines, N):
		(arr1, arr2) = ([], [])
		for line in lines:
			arr1.append(line[0])
			arr2.append(line[1])
		arr1.sort()
		arr2.sort()
		(i, j, ans, k) = (0, 0, 0, 0)
		while i < N and j < N:
			if arr1[i] <= arr2[j]:
				k += 1
				ans = max(ans, k)
				i += 1
			else:
				k -= 1
				j += 1
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		m = {}
		for i in lines:
			m[i[0]] = m.get(i[0], 0) + 1
			m[i[1] + 1] = m.get(i[1] + 1, 0) - 1
		ps = 0
		maxi = 0
		for i in sorted(m):
			ps += m[i]
			maxi = max(maxi, ps)
		return maxi


class Solution:

	def maxIntersections(self, lines, N):
		(st, en) = ([], [])
		for i in lines:
			st.append(i[0])
			en.append(i[1])
		st.sort()
		en.sort()
		(i, j, k, res) = (0, 0, 0, 0)
		while i < N and j < N:
			if st[i] <= en[j]:
				k += 1
				res = max(res, k)
				i += 1
			else:
				k -= 1
				j += 1
		return res


class Solution:

	def maxIntersections(self, lines, N):
		(a, pas, maax) = ({}, 0, 1)
		for (x1, x2) in lines:
			(a[x1], a[x2 + 1]) = (a.get(x1, 0) + 1, a.get(x2 + 1, 0) - 1)
		for i in sorted(a):
			(pas, maax) = (pas + a[i], max(maax, pas))
		return maax


class Solution:

	def maxIntersections(self, lines, N):
		q = {}
		for i in lines:
			q[i[0]] = q.get(i[0], 0) + 1
			q[i[1] + 1] = q.get(i[1] + 1, 0) - 1
		ps = 0
		mx = 1
		for i in sorted(q):
			ps += q[i]
			mx = max(mx, ps)
		return mx


class Solution:

	def maxIntersections(self, lines, n):
		start = list()
		end = list()
		for (s, e) in lines:
			start.append(s)
			end.append(e)
		start.sort()
		end.sort()
		i = j = 0
		inter = 0
		ans = 0
		while i < n and j < n:
			if start[i] <= end[j]:
				inter += 1
				ans = max(ans, inter)
				i += 1
			else:
				inter -= 1
				j += 1
		return ans


class Solution:

	def maxIntersections(self, lines, N):
		q = []
		for line in lines:
			q.extend([(line[0], -1), (line[1], 1)])
		q.sort()
		(ans, running) = (0, 0)
		for (_, status) in q:
			running -= status
			ans = max(ans, running)
		return ans