Overlapping Intervals/Ranges

 

Q: Given arbitrary ranges, merge all the ranges that overlap with each other. Return the resultant ranges.

<Solution>

1. Sort all the ranges by their start and end.

2. Now that we know that range's start increases we have to take care of the ends

--> We have to take care of the two cases below.

3. Code

ranges = []
ranges.append(schedules[0])
for s, e in schedules:
	if s <= ranges[-1][1]:
		ranges[-1][1] = max(ranges[-1][1], e)
	else:
		ranges.append([s, e])

 

LeetCode: 759. Employee Free Time

https://leetcode.com/problems/employee-free-time/description/

Employee Free Time - LeetCode

"""
# Definition for an Interval.
class Interval:
    def __init__(self, start: int = None, end: int = None):
        self.start = start
        self.end = end
"""

class Solution:
    def employeeFreeTime(self, schedule: '[[Interval]]') -> '[Interval]':
        schedules = []
        for i in range(len(schedule)):
            for j in range(len(schedule[i])):
                schedules.append([schedule[i][j].start, schedule[i][j].end])
        schedules.sort()
        ranges = []
        ranges.append(schedules[0])
        for s, e in schedules:
            if s <= ranges[-1][1]:
                ranges[-1][1] = max(ranges[-1][1], e)
            else:
                ranges.append([s, e])
        ret = []
        for i in range(1, len(ranges)):
            ret.append(Interval(ranges[i-1][1], ranges[i][0]))
        return ret