Is Overlap

Detects whether the two intervals overlap

O(1)

Python | Java

	case 1: no overlap case 2: overlap case 3: overlap
	l r l
	---- b a ----- a ------------
	a ---- ----- b ---- b
	r l r
	def isOverlap(a: List[int], b: List[int]) -> bool:
	l = max(a[0], b[0])
	r = min(a[1], b[1])
	return l <= r

view raw IsOverlap.py hosted with ❤ by GitHub

	case 1: no overlap case 2: overlap case 3: overlap
	l r l
	---- b a ----- a ------------
	a ---- ----- b ---- b
	r l r
	public boolean isOverlap(int[] a, int[] b) {
	int l = Math.max(a[0], b[0]);
	int r = Math.min(a[1], b[1]);
	return l <= r;
	}

view raw IsOverlap.java hosted with ❤ by GitHub

Detects whether there's an intersection between the two intervals (lines).

LeetCode

252. Meeting Rooms

Python | Java

	def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
	def isOverlap(a: List[int], b: List[int]) -> bool:
	l = max(a[0], b[0])
	r = min(a[1], b[1])
	return l < r
	if len(intervals) <= 1: return True
	intervals.sort()
	cur = intervals[0]
	for i in range(1, len(intervals)):
	if isOverlap(cur, intervals[i]): return False
	cur = intervals[i]
	return True

view raw MeetingRooms.py hosted with ❤ by GitHub

	public boolean canAttendMeetings(int[][] intervals) {
	if (intervals.length <= 1) return true;
	Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
	int[] cur = intervals[0];
	for (int i = 1; i < intervals.length; i++) {
	if (isOverlap(cur, intervals[i]) == true) return false;
	cur = intervals[i];
	}
	return true;
	}
	private boolean isOverlap(int[] a, int[] b) {
	int l = Math.max(a[0], b[0]);
	int r = Math.min(a[1], b[1]);
	return l < r;
	}

view raw MeetingRooms.java hosted with ❤ by GitHub

• Relevant Problems

  https://leetcode.com/problems/meeting-rooms/

  https://leetcode.com/problems/merge-intervals/

  https://leetcode.com/problems/interval-list-intersections/