Data Stream As Disjoint Intervals - Leetcode Solution

Problem Statement:

Given an integer stream, we must maintain a running list of disjoint intervals and we must be able to insert a new integer into the stream at any time. Whenever a new integer is inserted into the stream, we must output the newly formed list of disjoint intervals.

Example:

Input: insert(1), Output: [1,1] insert(3), Output: [1,1],[3,3] insert(7), Output: [1,1],[3,3],[7,7] insert(2), Output: [1,3],[7,7] insert(10), Output: [1,3],[7,7],[10,10],[12,16]

Solution:

We start with an empty list of disjoint intervals. Whenever a new integer is inserted into the stream, we check if it can be merged with any of the existing intervals. If merging is possible, we merge the intervals. If not, we add the interval as a new disjoint interval.

We can use a list of tuples to represent the disjoint intervals where each tuple represents an interval with a start and an end value.

Algorithm:

1. Start with an empty list of disjoint intervals.
2. Loop through the integer stream:
   1. Check if the integer can be merged with any of the existing intervals:
      1. If merged, update the merged interval.
      2. If not merged, add the current interval as a new disjoint interval.
   2. Sort the disjoint intervals based on their start value.
   3. Output the current list of disjoint intervals.

Python Code:

class Interval: def init(self, start, end): self.start = start self.end = end

def insert(interval, num): #check if num can be merged with any of the intervals for i in range(len(interval)): if num >= interval[i].start and num <= interval[i].end: return #num is already within an interval if num == interval[i].start - 1: interval[i].start = num return #merged with previous interval elif num == interval[i].end + 1: interval[i].end = num #check if merged with the next interval also if i < len(interval)-1 and interval[i].end == interval[i+1].start - 1: interval[i].end = interval[i+1].end interval.pop(i+1) return #merged with next interval elif num < interval[i].start - 1: interval.insert(i, Interval(num, num)) return #new interval inserted in the list interval.append(Interval(num, num)) #all intervals merged, add as a new interval

def disjoint_intervals(nums): intervals = [] for num in nums: insert(intervals, num) #sort the intervals based on their start value intervals.sort(key = lambda x: x.start) #print the current list of disjoint intervals print([[i.start, i.end] for i in intervals])

#Test Case disjoint_intervals([1,3,7,2,10]) #expected output: [[1,3],[7,7]], [[10,10]]

1