Fooland city has a special multi-lane running track. Lanes are numbered from 1 to Tracks. The lanes have N horizontal barriers lying on it (due to some digging and construction work). The i^{th }barrier cover lanes from Li1 to Li2 (both inclusive). Also, the barriers may overlap. The athletes can’t run on the lanes on which barriers are present because they aren’t allowed to switch lanes anytime in the race. (Once a particular lane is allotted to an athlete he/she can’t switch his/her lane anytime during the race and there can be only one athlete on each lane.)
Now the race has to be organised tomorrow itself and the digging work could not be finished on time. The race would have to be organised on the same track only because Fooland city doesn’t have any other track. Help organizers in finding out how many athletes can run in a single race so that none of them would have to switch lanes.
 
Example 1:
Input:
N = 5, Track = 20
L_{i} = {(1 3), (5 8), (8 13), 
           (14 15), (9 12)}
Output:
6
Explanation:
The barriers cover lanes from
 1 to 3, 5 to 8, 8 to 13, 
14 to 15 and 9 to 12. Hence, 
barriers are present on the 
lanes: {1, 2, 3, 5, 6, 7, 8,
 9, 10, 11, 12, 13, 14, 15}.
Hence, the lanes which doesn't
come under any barriers are 
{4, 16, 17, 18, 19, 20}.
So, there are 6 lanes on which
athletes can run – {4, 16, 17,
    18, 19, 20}
 
Your Task:  
You don't need to read input or print anything. Your task is to complete the function emptyLanes() which takes the pair array A[], its size N and an integer Tracks as inputs and returns the number of athletes that can run in a single track.
Expected Time Complexity: O(N)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤ 10^{6}
1 ≤ Tracks ≤ 10^{6}
1 ≤ Li1 ≤ Li2 ≤ Tracks
The Barriers may overlap.

Source: geeksforgeeks | Difficulty: EASY
Tags: Sorting

Data structures

Starter code: #User function Template for python3

class Solution:
    def emptyLanes(self, a, n, tracks):
    # list a contains pairs, example
    # a = [[1,2], [3,4], [5,6]] 
    # Your code goes here



Solutions:
class Solution:

	def emptyLanes(self, arr, n, tracks):
		arr.sort()
		res = 0
		for i in range(1, len(arr)):
			if arr[res][1] >= arr[i][0]:
				arr[res][0] = min(arr[res][0], arr[i][0])
				arr[res][1] = max(arr[res][1], arr[i][1])
			else:
				res += 1
				arr[res] = arr[i]
		ans = 0
		if arr[0][0] != 1:
			ans += arr[0][0] - 1
		for i in range(res):
			if abs(arr[i][1] - arr[i + 1][0]) > 1:
				ans += abs(arr[i][1] - arr[i + 1][0]) - 1
		if arr[res][1] < tracks:
			ans += abs(arr[res][1] - tracks)
		return ans


class Solution:

	def emptyLanes(self, a, n, tracks):
		a = sorted(a, key=lambda x: x[0])
		start = a[0][0]
		end = a[0][1]
		su = end - start + 1
		for i in range(1, n):
			x = a[i][0]
			y = a[i][1]
			if x > end:
				end = y
				su += end - x + 1
			elif x <= end and y > end:
				su += y - end
				end = y
		return tracks - su


class Solution:

	def emptyLanes(self, a, n, tracks):
		count = 0
		a.sort(reverse=True)
		for i in range(1, tracks + 1):
			while a and a[-1][1] < i:
				a.pop()
			if not a or i < a[-1][0]:
				count += 1
		return count


class Solution:

	def emptyLanes(self, a, n, tracks):
		mx = max([i[1] for i in a])
		fenc = [0] * (tracks + 1)
		for i in a:
			fenc[i[0] - 1] += 1
			fenc[i[1]] -= 1
		for i in range(1, tracks + 1):
			fenc[i] += fenc[i - 1]
		return fenc.count(0) - 1


class Solution:

	def emptyLanes(self, a, n, tracks):
		a.sort()
		barrier_ends = a[0][1]
		ans = a[0][0] - 1
		for i in range(1, n):
			if a[i][0] > barrier_ends:
				ans += a[i][0] - barrier_ends - 1
			barrier_ends = max(barrier_ends, a[i][1])
		ans += tracks - barrier_ends
		return ans