Given an 2D array intervals of size N representing intervals where intervals [ i ] = [start_{i} , end_{i }), return the minimum number of intervals you need to remove to make the rest of the intervals non-overlapping.
 
Example 1:
Input:
N = 4
intervals [ ] = {{1, 2}, {2, 3}, {3, 4}, {1, 3}}
Output: 1
Explanation: 
{1, 3} can be removed and the rest of the intervals are non-overlapping.
 
Example 2:
Input:
N = 3
intervals [ ] = {{1, 3}, {1, 3}, {1, 3}}
Output: 2
Explanation: 
You need to remove two {1, 3} to make the rest of the intervals non-overlapping.
 
Your Task:
You don't need to read input or print anything. Your task is to complete the function minRemoval() which takes the interger N and 2D integer array intervals [ ] as parameters and returns the minimum number of intervals needs to remove in order to make the remaining intervals non-overlapping.
Expected Time Complexity: O(NlogN)
Expected Auxiliary Space: O(1)
Constraints:
1 ≤ N ≤  10^{5}
|intervals_{i}| == 2
-5*10^{4 }≤ start_{i }< end_{i} <=5*10^{4}

Source: geeksforgeeks | Difficulty: MEDIUM
Tags: Sorting

Data structures

Greedy algorithms

Starter code: #User function Template for python3



class Solution:

    def minRemoval(self, N, intervals):

        # Code here

Solutions:
class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda i: i[1])
		st = intervals[0][0]
		en = intervals[0][1]
		c = 0
		s = 0
		e = 0
		i = 1
		while i < N:
			s = intervals[i][0]
			e = intervals[i][1]
			if s < en:
				c += 1
			else:
				st = s
				en = e
			i += 1
		return c


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: (x[1], x[0]))
		prev = intervals[0]
		ans = 0
		for i in range(1, N):
			if prev[1] <= intervals[i][0]:
				prev = intervals[i]
			else:
				ans += 1
		return ans


class Solution:

	def minRemoval(self, N, intervals):
		intervals = sorted(intervals, key=lambda x: x[0])
		curr_interval = intervals[0]
		count = 0
		for i in range(1, N):
			if curr_interval[1] <= intervals[i][0]:
				curr_interval = intervals[i]
			else:
				count += 1
				if curr_interval[1] > intervals[i][1]:
					curr_interval = intervals[i]
		return count


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[1])
		ans = []
		ans.append(intervals[0])
		for i in range(1, N):
			if ans[-1][1] > intervals[i][0]:
				continue
			else:
				ans.append(intervals[i])
		return len(intervals) - len(ans)


class Solution:

	def minRemoval(self, N, intervals):
		if N == 1:
			return 0
		count = 0
		intervals.sort(key=lambda i: i[1])
		res = intervals[0][1]
		for (s, t) in intervals[1:]:
			if s >= res:
				res = t
			else:
				count += 1
		return count


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda i: i[1])
		temp_it = intervals[0]
		res = 0
		for i in range(1, len(intervals)):
			if temp_it[1] > intervals[i][0]:
				res += 1
			else:
				temp_it = intervals[i]
		return res


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort()
		res = 0
		lastEnd = intervals[0][1]
		for (start, end) in intervals[1:]:
			if start >= lastEnd:
				lastEnd = end
			else:
				res += 1
				lastEnd = min(lastEnd, end)
		return res


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort()
		prev_end = intervals[0][1]
		res = 0
		for i in range(1, N):
			if intervals[i][0] >= prev_end:
				prev_end = intervals[i][1]
			else:
				res += 1
				prev_end = min(prev_end, intervals[i][1])
		return res


class Solution:

	def minRemoval(self, N, intervals):
		count = 0
		intervals.sort(key=lambda x: x[1])
		s = intervals[0][0]
		e = intervals[0][1]
		for (i, j) in intervals[1:]:
			if i < e:
				count += 1
			elif i >= e:
				s = i
				e = j
		return count


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[0])
		prev = intervals[0][1]
		count = 0
		for i in intervals[1:]:
			if prev <= i[0]:
				prev = i[1]
			else:
				count += 1
				prev = min(prev, i[1])
		return count


class Solution:

	def minRemoval(self, N, arr):
		arr.sort()
		stack = []
		cnt = 0
		for item in arr:
			(currs, currend) = item
			if len(stack) == 0:
				stack.append((currs, currend))
			else:
				(prevs, prevend) = stack.pop()
				if currs >= prevend:
					stack.append((prevs, prevend))
					stack.append((currs, currend))
				else:
					if prevend < currend:
						stack.append((prevs, prevend))
					else:
						stack.append((currs, currend))
					cnt += 1
		return cnt


class Solution:

	def minRemoval(self, N, intervals):
		intervals = sorted(intervals, key=lambda x: x[1])
		prev_s = intervals[0][0]
		prev_e = intervals[0][1]
		count = 0
		for (s, e) in intervals:
			if s < prev_e:
				pass
			else:
				prev_s = s
				prev_e = e
				count += 1
		return N - count - 1


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[1])
		endTime = float('-inf')
		c = 0
		for x in intervals:
			if endTime <= x[0]:
				endTime = x[1]
			else:
				c += 1
		return c


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[1])
		end = intervals[0][1]
		ct = 0
		for i in range(1, N):
			st = intervals[i][0]
			if st < end:
				ct += 1
			else:
				end = intervals[i][1]
		return ct


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[1])
		cnt = 0
		temp = intervals[0][1]
		for i in range(1, N):
			if intervals[i][0] >= temp:
				temp = intervals[i][1]
			else:
				cnt += 1
		return cnt


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[0])
		i = 1
		ans = 0
		end = intervals[0][1]
		while i < len(intervals):
			if intervals[i][0] < end:
				ans += 1
				if end > intervals[i][1]:
					end = intervals[i][1]
			else:
				end = intervals[i][1]
			i += 1
		return ans


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[1])
		pos = 0
		count = 0
		i = 1
		while i < len(intervals):
			if intervals[i][0] < intervals[pos][1]:
				count += 1
			else:
				pos = i
			i += 1
		return count


class Solution:

	def minRemoval(self, N, intervals):
		intervals = sorted(intervals)
		l = 0
		r = 1
		count = 0
		while r < len(intervals):
			if intervals[l][1] <= intervals[r][0]:
				l = r
				r += 1
			elif intervals[l][1] <= intervals[r][1]:
				r += 1
				count += 1
			elif intervals[l][1] > intervals[r][1]:
				l = r
				r += 1
				count += 1
		return count


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[1])
		m = intervals[0][1]
		c = 0
		for i in range(1, N):
			if intervals[i][0] >= m:
				m = intervals[i][1]
			else:
				c += 1
		return c


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[1])
		count = 0
		i = 0
		for j in range(1, len(intervals)):
			if intervals[i][1] > intervals[j][0]:
				count += 1
			else:
				i = j
		return count


class Solution:

	def minRemoval(self, N, intervals):
		intervals.sort(key=lambda x: x[1])
		count = 0
		time = float('-inf')
		for (start, end) in intervals:
			if start < time:
				count += 1
			else:
				time = end
		return count


class Solution:

	def minRemoval(self, N, intervals):
		(end, cnt) = (float('-inf'), 0)
		for (s, e) in sorted(intervals, key=lambda x: x[1]):
			if s >= end:
				end = e
			else:
				cnt += 1
		return cnt


class Solution:

	def minRemoval(self, N, intervals):
		if N == 1:
			return 0
		ans = 0
		intervals.sort(key=lambda i: i[1])
		res = intervals[0][1]
		for (i, j) in intervals[1:]:
			if i >= res:
				res = j
			else:
				ans += 1
		return ans


class Solution:

	def minRemoval(self, N, ranges):
		size = len(ranges)
		rem = 0
		ranges.sort()
		end = ranges[0][1]
		for i in range(1, size):
			if ranges[i][0] < end:
				rem += 1
				end = min(ranges[i][1], end)
			else:
				end = ranges[i][1]
		return rem


class Solution:

	def minRemoval(self, n, arr):
		arr.sort(key=lambda x: x[1])
		i = 0
		j = 1
		count = 1
		while j != n:
			if arr[i][1] <= arr[j][0]:
				i = j
				j += 1
				count += 1
			else:
				j += 1
		return n - count


class Solution:

	def minRemoval(self, N, Intervals):
		intervals = sorted(Intervals, key=lambda x: x[0])
		q = [intervals[0]]
		c = 0
		for i in range(1, len(intervals)):
			if q[-1][1] > intervals[i][0]:
				(a, b) = q.pop()
				q.append([a, min(b, intervals[i][1])])
				c += 1
			else:
				q.append(intervals[i])
		return c


class Solution:

	def minRemoval(self, n, intervals):
		if len(intervals) == 0:
			return 0
		intervals = sorted(intervals, key=lambda x: x[1])
		(removeNum, curBorder) = (0, intervals[0][1])
		for interval in intervals[1:]:
			if interval[0] < curBorder:
				removeNum += 1
			else:
				curBorder = interval[1]
		return removeNum


class Solution:

	def minRemoval(self, N, intervals):
		if not intervals or N == 0:
			return 0
		intervals.sort()
		prevEnd = intervals[0][1]
		cnt = 0
		for i in range(1, N):
			if prevEnd > intervals[i][0]:
				cnt += 1
				prevEnd = min(prevEnd, intervals[i][1])
			else:
				prevEnd = intervals[i][1]
		return cnt