There are N jobs and the start and finish time of the jobs are given in arrays start[] and end[] respectively. Each job requires one laptop and laptops can't be shared. Find the minimum number of laptops required given that you can give your laptop to someone else when you are not doing your job.
Example 1:
Input:
N = 3
start[] = {1, 2, 3}
end[] = {4, 4, 6}
Output:
3
Explanation:
We can clearly see that everyone's supposed to
be doing their job at time 3. So, 3 laptops
will be required at minimum.
Example 2:
Input:
N = 3
start[] = {1, 5, 2}
end[] = {2, 6, 3}
Output :
1
Explanation:
All jobs can be done using 1 laptop only.
Your Task:  
You don't need to read input or print anything. Your task is to complete the function minLaptops() which takes an integer N and two arrays start and end denoting starting and ending time of N jobs and returns minimum laptops required.
Expected Time Complexity: O(N*logN)
Expected Auxiliary Space: O(N)
Constraints:
1 ≤ N ≤ 10^{5 }
1^{ }≤ start[i] < end[i] ≤ 10^{9}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Starter code: #User function Template for python3



class Solution: 

    def minLaptops(self, N, start, end):

        # Code here

Solutions:
from collections import deque
import bisect

class Solution:

	def minLaptops(self, n, start, end):
		arr = list(zip(start, end))
		arr.sort()
		count = 0
		s = deque()
		for i in range(n):
			if s and arr[i][0] >= s[0]:
				s.popleft()
			bisect.insort_left(s, arr[i][1])
		return len(s)


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		i = 0
		j = 1
		result = 1
		while j < N:
			if start[j] < end[i]:
				result += 1
				j += 1
			else:
				i += 1
				j += 1
		return result


class Solution:

	def minLaptops(self, n, start, end):
		start.sort()
		end.sort()
		i = 1
		j = 0
		total = 1
		while i < n and j < n:
			if end[j] - start[i] > 0:
				total += 1
			else:
				j += 1
			i += 1
		return total


class Solution:

	def minLaptops(self, n, start, end):
		c = 0
		start.sort()
		end.sort()
		i = 0
		j = 0
		ans = 0
		while i < n:
			if start[i] < end[j]:
				c += 1
				ans = max(ans, c)
				i += 1
			else:
				c -= 1
				j += 1
		return ans


import heapq

class Solution:

	def minLaptops(self, N, start, end):
		comps = sorted(zip(start, end))
		heap = []
		ans = 0
		items = 0
		for i in range(N):
			if not heap:
				heapq.heappush(heap, comps[i][1])
				items = 1
			else:
				while heap and heap[0] <= comps[i][0]:
					heapq.heappop(heap)
					items -= 1
				heapq.heappush(heap, comps[i][1])
				items += 1
			ans = max(ans, items)
		return ans


class Solution:

	def minLaptops(self, N, start, end):
		arr = start.copy()
		dep = end.copy()
		arr.sort()
		dep.sort()
		count = 0
		mx = -9999999
		i = 0
		j = 0
		while i < N:
			if arr[i] < dep[j]:
				count += 1
				mx = max(mx, count)
				i += 1
			elif arr[i] >= dep[j]:
				count -= 1
				j += 1
		return mx


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		total = 0
		m = 0
		i = 0
		j = 0
		while i < N and j < N:
			if start[i] < end[j]:
				i += 1
				total += 1
			else:
				j += 1
				total -= 1
			m = int(max(m, total))
		return m


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		ans = 0
		count = 0
		i = 0
		j = 0
		while i < N:
			if start[i] < end[j]:
				count += 1
				i += 1
				ans = max(ans, count)
			elif start[i] >= end[j]:
				count -= 1
				j += 1
		return ans


import heapq as h

class Solution:

	def minLaptops(self, N, start, end):
		l = [[start[i], end[i]] for i in range(N)]
		l.sort()
		l1 = []
		h.heapify(l1)
		count = 0
		m = 0
		for i in l:
			if len(l1) == 0:
				count = count + 1
				h.heappush(l1, i[1])
				continue
			if l1[0] <= i[0]:
				x = h.heappop(l1)
				h.heappush(l1, i[1])
				continue
			h.heappush(l1, i[1])
			count = count + 1
		return count


class Solution:

	def minLaptops(self, N, start, end):
		a = []
		for i in range(N):
			a.append([start[i], 1])
			a.append([end[i], 0])
		a.sort()
		max1 = 0
		c = 0
		for i in a:
			if i[1] == 1:
				c += 1
				max1 = max(max1, c)
			else:
				c -= 1
		return max1


import heapq

class Solution:

	def minLaptops(self, N, start, end):
		nums = []
		for i in range(N):
			nums.append([start[i], end[i]])
		nums.sort(key=lambda x: x[0])
		hp = []
		for i in range(N):
			if hp and nums[i][0] >= hp[0][0]:
				heapq.heappop(hp)
			heapq.heappush(hp, (nums[i][1], nums[i][0]))
		return len(hp)


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		maxi = 0
		count = 0
		j = 0
		for i in range(N):
			count += 1
			maxi = max(maxi, count)
			while i < N - 1 and j < N and (end[j] <= start[i + 1]):
				count -= 1
				j += 1
		return maxi


class Solution:

	def minLaptops(self, N, start, end):
		mp = dict()
		for i in start:
			if i in mp:
				mp[i] += 1
			else:
				mp[i] = 1
		for i in end:
			if i in mp:
				mp[i] += -1
			else:
				mp[i] = -1
		c = ans = 0
		for i in sorted(mp):
			c += mp[i]
			ans = max(ans, c)
		return ans


import heapq

class Solution:

	def minLaptops(self, N, start, end):
		arr = []
		for i in range(N):
			arr.append([start[i], end[i]])
		arr.sort()
		ans = 1
		en = []
		heapq.heappush(en, arr[0][1])
		for i in range(1, N):
			if arr[i][0] < en[0]:
				ans += 1
				heapq.heappush(en, arr[i][1])
			else:
				heapq.heappop(en)
				heapq.heappush(en, arr[i][1])
		return ans


class Solution:

	def minLaptops(self, N, start, end):
		op = [0] * (N * 2)
		for i in range(N):
			op[i] = [start[i], 1]
		a = 0
		for i in range(N, 2 * N):
			op[i] = [end[a], -1]
			a += 1
		srn = sorted(op)
		pre = [0] * (N * 2)
		pre[0] = srn[0][1]
		for i in range(1, len(op)):
			pre[i] = pre[i - 1] + srn[i][1]
		return max(pre)


class Solution:

	def minLaptops(self, N, start, end):
		arr = []
		for i in range(N):
			arr.append([start[i], 1])
			arr.append([end[i], -1])
		arr.sort()
		maxi = 0
		s = 0
		for i in range(len(arr)):
			s += arr[i][1]
			maxi = max(maxi, s)
		return maxi


class Solution:

	def minLaptops(self, N, arr, dep):
		l1 = []
		for i in arr:
			l = []
			l.append(i)
			l.append(1)
			l1.append(l)
		for i in dep:
			l = []
			l.append(i)
			l.append(-1)
			l1.append(l)
		l1.sort()
		s = 0
		l2 = []
		for i in l1:
			l2.append(i[1])
		l3 = []
		for i in l2:
			s = s + i
			l3.append(s)
		return max(l3)


from collections import deque
import bisect

class Solution:

	def minLaptops(self, n, start, end):
		a = list(zip(start, end))
		a.sort()
		c = 0
		r = deque()
		for i in range(n):
			if r and a[i][0] >= r[0]:
				r.popleft()
			bisect.insort_left(r, a[i][1])
		return len(r)


class Solution:

	def minLaptops(self, N, start, end):
		both = [[i, j] for (i, j) in zip(start, end)]
		lis = []
		for (i, j) in zip(start, end):
			lis.append([i, 1])
			lis.append([j, -1])
		mx = 0
		c = 0
		lis.sort()
		for i in range(len(lis)):
			c += lis[i][1]
			mx = max(mx, c)
		return mx


class Solution:

	def minLaptops(self, N, start, end):
		res = []
		for i in range(N):
			res.append([start[i], 1])
			res.append([end[i], -1])
		res.sort()
		ress = 0
		x = 0
		for i in res:
			x += i[1]
			ress = max(ress, x)


class Solution:

	def minLaptops(self, N, start, end):
		mx = 1
		ans = []
		for i in range(N):
			ans.append((start[i], 1))
			ans.append((end[i], -1))
		ans.sort()
		px = ans[0][1]
		for i in range(1, 2 * N):
			px += ans[i][1]
			if px > mx:
				mx = px
		return mx


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		j = 0
		c = 0
		for i in range(0, N):
			if start[i] < end[j]:
				c += 1
			else:
				j += 1
		return c


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		res = 0
		i = 0
		j = 0
		while i != N:
			if end[j] <= start[i]:
				j += 1
				i += 1
			elif end[j] > start[i]:
				i += 1
				res += 1
		return res


import heapq

class Solution:

	def minLaptops(self, N, start, end):
		arr = sorted(zip(start, end), key=lambda x: x[0])
		new = []
		ans = 0
		for i in arr:
			if len(new) == 0:
				heapq.heappush(new, i[1])
			elif new[0] > i[0]:
				heapq.heappush(new, i[1])
			else:
				heapq.heappop(new)
				heapq.heappush(new, i[1])
			ans = max(ans, len(new))
		return ans


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		i = 1
		j = 0
		ans = 1
		res = 1
		while i < N and j < N:
			if start[i] < end[j]:
				ans += 1
			else:
				res = max(ans, res)
				res -= 1
				j += 1
			i += 1
		return max(ans, res)


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		count = 0
		m = 0
		for i in range(N):
			if start[i] < end[m]:
				count += 1
			else:
				m += 1
		return count


class Solution:

	def minLaptops(self, N, start, end):
		time_schedule = dict()
		maximum = -1000000000.0
		for i in range(N):
			if start[i] in time_schedule:
				time_schedule[start[i]] += 1
			else:
				time_schedule[start[i]] = 1
			if end[i] in time_schedule:
				time_schedule[end[i]] -= 1
			else:
				time_schedule[end[i]] = -1
		current = 0
		time_line = start + end
		time_line = list(set(time_line))
		time_line.sort()
		for v in time_line:
			current += time_schedule[v]
			maximum = max(current, maximum)
		return maximum


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		c = 0
		i = 0
		j = 0
		lap = 0
		while i < N:
			if start[i] < end[j]:
				c += 1
				i += 1
				lap = max(c, lap)
			else:
				c -= 1
				j += 1
		return lap


import heapq

class Solution:

	def minLaptops(self, N, start, end):
		ans = 0
		heap = []
		for (s, e) in sorted(zip(start, end)):
			while heap and heap[0] <= s:
				heapq.heappop(heap)
			heapq.heappush(heap, e)
			ans = max(ans, len(heap))
		return ans


class Solution:

	def minLaptops(self, N, start, end):
		start = sorted(start)
		end = sorted(end)
		running = 1
		st = 1
		fn = 0
		while st < N and fn < N:
			if start[st] < end[fn]:
				running += 1
			else:
				fn += 1
			st += 1
		return running


import bisect

class Solution:

	def minLaptops(self, N, start, end):
		time = {}
		for t in start:
			if t not in time:
				time[t] = 0
			time[t] += 1
		for t in end:
			if t not in time:
				time[t] = 0
			time[t] -= 1
		ans = 0
		cur = 0
		for t in sorted(time):
			cur += time[t]
			ans = max(ans, cur)
		return ans


import heapq

class Solution:

	def __init__(self):
		self.heap = list()

	def find_number_of_finished_jobs(self, current_time):
		finished_jobs_count = 0
		while self.heap:
			if self.heap[0] <= current_time:
				heapq.heappop(self.heap)
				finished_jobs_count += 1
			else:
				break
		return finished_jobs_count

	def minLaptops(self, N, start, end):
		max_laptops = 1
		laptops_in_use = 0
		job_times = sorted(zip(start, end))
		for (current_time, end_time) in job_times:
			laptops_in_use += 1
			heapq.heappush(self.heap, end_time)
			finished_jobs_count = self.find_number_of_finished_jobs(current_time)
			laptops_in_use -= finished_jobs_count
			max_laptops = max(max_laptops, laptops_in_use)
		return max_laptops


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		count = 1
		i = 1
		j = 0
		while i < N and j < N:
			if end[j] - start[i] > 0 or start[i] < end[j]:
				count += 1
				i += 1
			else:
				i += 1
				j += 1
		return count


class Solution:

	def minLaptops(self, n, start, end):
		start.sort()
		end.sort()
		res = 1
		s = 1
		e = 0
		while s < n and e < n:
			diff = end[e] - start[s]
			if diff > 0:
				res += 1
				s += 1
			else:
				s += 1
				e += 1
		return res


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		tot = 0
		endIdx = 0
		for i in range(N):
			if start[i] < end[endIdx]:
				tot += 1
			else:
				endIdx += 1
			if endIdx >= N:
				break
		return tot


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		(tot, maxi, i, j) = (0, 0, 0, 0)
		while i < N and j < N:
			if start[i] < end[j]:
				i += 1
				tot += 1
			else:
				j += 1
				tot -= 1
			maxi = max(maxi, tot)
		return maxi


class Solution:

	def minLaptops(self, N, start, end):
		mp = {}
		for i in range(N):
			if start[i] in mp:
				mp[start[i]] += 1
			else:
				mp[start[i]] = 1
			if end[i] in mp:
				mp[end[i]] -= 1
			else:
				mp[end[i]] = -1
		result = 0
		c = 0
		for i in sorted(mp):
			c += mp[i]
			result = max(result, c)
		return result


class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		(i, j) = (0, 0)
		(reqLaptop, maxReq) = (0, 0)
		while i < N and j < N:
			if start[i] < end[j]:
				reqLaptop = reqLaptop + 1
				i = i + 1
			else:
				reqLaptop = reqLaptop - 1
				j = j + 1
			maxReq = max(reqLaptop, maxReq)
		return maxReq


class Solution:

	def minLaptops(self, N, start, end):
		d = dict()
		if N == 1:
			return 1
		for i in range(N):
			d[start[i]] = 1 + d.get(start[i], 0)
			d[end[i]] = -1 + d.get(end[i], 0)
		r = [(i, d[i]) for i in d]
		r.sort()
		res = 0
		curr = 0
		for (i, j) in r:
			curr += j
			res = max(res, curr)
		return res


from heapq import heapify, heappush, heappop, nsmallest

class Solution:

	def minLaptops(self, N, start, end):
		i = 0
		j = 0
		lappy = 0
		maxLap = 0
		start.sort()
		end.sort()
		while i < N and j < N:
			if start[i] < end[j]:
				i += 1
				lappy += 1
			else:
				j += 1
				lappy -= 1
			maxLap = max(maxLap, lappy)
		return maxLap


from collections import OrderedDict

class Solution:

	def minLaptops(self, N, start, end):
		start.sort()
		end.sort()
		count = 1
		i = 1
		j = 0
		while i < N:
			if end[j] > start[i]:
				count += 1
			else:
				j += 1
			i += 1
		return count


class Solution:

	def sortFun(val):
		return val[0]

	def minLaptops(self, N, start, end):
		(arr1, arr2) = (['s'] * N, ['e'] * N)
		arr1 = list(zip(start, arr1))
		arr2 = list(zip(end, arr2))
		temp = arr2 + arr1
		temp.sort(key=Solution.sortFun)
		count = 0
		max_count = 0
		for item in temp:
			if item[1] == 's':
				count += 1
			else:
				count -= 1
			if count > max_count:
				max_count = count
		return max_count