Teaching Kids Programming – Longest Interval Algorithm


Teaching Kids Programming: Videos on Data Structures and Algorithms

You are given a two-dimensional list of integers intervals where each list represents an inclusive [start, end] interval. Return the longest interval that you can make by merging any number of intersecting intervals.

Constraints
n ≤ 100,000 where n is the length of intervals
Example 1
Input

1
2
3
4
5
6
7
intervals = [
    [1, 5],
    [3, 8],
    [4, 5],
    [10, 13],
    [15, 17]
]
intervals = [
    [1, 5],
    [3, 8],
    [4, 5],
    [10, 13],
    [15, 17]
]

Output
8
Explanation
After merging, we have the interval [1, 8] which has a length of 8

Longest Interval Algorithm

We can sort the intervals by the start and then end point in O(NLogN) where N is the number of intervals. Then, we can iterate the intervals one by one from left to the right. If the new interval is disjoint then the current interval (the new start is larger than the current end), then we update the current start point.

We update the current end point if the new end is larger. Then we know the current combined interval – and update the answer if it is longer.

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def solve(self, intervals):
        if not intervals:
            return 0
        intervals.sort()
        start, end = intervals[0]
        ans = end - start + 1
        for a, b in intervals[1:]:
            if a > end:
                start = a                
            end = max(end, b)
            ans = max(ans, end - start + 1)
        return ans
class Solution:
    def solve(self, intervals):
        if not intervals:
            return 0
        intervals.sort()
        start, end = intervals[0]
        ans = end - start + 1
        for a, b in intervals[1:]:
            if a > end:
                start = a                
            end = max(end, b)
            ans = max(ans, end - start + 1)
        return ans

The overall time complexity is O(NLogN) due to sorting.

See also: Teaching Kids Programming – Compute the Intersection of the Intervals

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
365 words
Last Post: Teaching Kids Programming - Beer Bottle Exchange Algorithm via Simulation
Next Post: Algorithm to Compute the Maximum Population Year

The Permanent URL is: Teaching Kids Programming – Longest Interval Algorithm

Leave a Reply