Find maximum path in interval list

Question

Given a list of intervals, find the maximum path length that can be formed by connecting overlapping intervals. The input consists of an array of intervals, where each interval is represented as a pair of integers [start, end]. The output should be a single integer representing the maximum path length.

Codemia · Accepted Answer

The problem at hand requires finding the maximum path length that can be formed by connecting overlapping intervals. This suggests the need for a method to systematically evaluate overlapping intervals and compute the total length of the connected paths. The two-pointer approach is particularly suitable here as it allows for efficient traversal through the sorted intervals, enabling us to determine overlaps and calculate the cumulative lengths without needing to re-evaluate previously considered intervals.

1. **Sort the Intervals**: Start by sorting the list of intervals based on the start time. For example, if the intervals are [[1, 3], [2, 5], [6, 8]], sorting them results in the same order as they are already sorted. 
2. **Initialize Pointers**: Use two pointers, `current_start` and `current_end`, initialized to the start and end of the first interval. 
3. **Iterate Through Intervals**: Loop through the sorted intervals. For each interval, check if it overlaps with the current interval represented by `current_start` and `current_end`. 
   - If it overlaps (i.e., the start of the current interval is less than or equal to `current_end`), update `current_end` to be the maximum of `current_end` and the end of the current interval. This accounts for the overlapping region. 
   - If it does not overlap, calculate the path length from `current_start` to `current_end`, update the maximum length if necessary, and then reset `current_start` and `current_end` to the current interval. 
4. **Final Calculation**: After the loop, ensure to calculate the length for the last segment as it may not have been accounted for. 
5. **Return the Maximum Length**.

```python
from typing import List

def max_path_length(intervals: List[List[int]]) -> int:
    if not intervals:
        return 0
    
    # Step 1: Sort intervals by their start times
    intervals.sort(key=lambda x: x[0])
    
    max_length = 0
    current_start = intervals[0][0]
    current_end = intervals[0][1]
    
    # Step 3: Iterate through sorted intervals
    for start, end in intervals[1:]:
        if start <= current_end:  # Overlap detected
            current_end = max(current_end, end)  # Extend the end if needed
        else:  # No overlap
            max_length = max(max_length, current_end - current_start)  # Update max length
            current_start = start  # Move to the next interval
            current_end = end
    
    # Final check for the last segment
    max_length = max(max_length, current_end - current_start)
    return max_length
```

The time complexity of this solution is O(n log n) due to the sorting step, where n is the number of intervals. The subsequent loop runs in O(n) to process each interval, so the overall complexity remains dominated by the sorting step. The space complexity is O(1) if we consider the input intervals as part of the input space, otherwise O(n) if we account for storing the sorted intervals.

1. **Empty Input**: If the input list is empty, the function should return 0. 
2. **Single Interval**: If there is only one interval, the output should be the length of that interval. 
3. **No Overlaps**: If all intervals are disjoint, the function should return the length of the largest single interval. For example, for intervals [[1, 2], [3, 4], [5, 6]], the result should be 2 (the length of [5, 6]). 
4. **Fully Overlapping Intervals**: For intervals like [[1, 5], [2, 3]], the maximum path length would be 4 (from 1 to 5). 
5. **Identical Start and End**: Intervals like [[1, 1], [1, 1]] should still correctly compute the path length.

Find maximum path in interval list

JPMorgan

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Sharpen Your Skills on Codemia

Sample Answer

Problem Analysis

Approach

Submit Your Answer

JPMorgan Machine Learning Engineer Interview Guide

Related Questions

Binary Search on graph

Count kth largest element in array

Find connected components in string

Merge Three Sorted strings

Binary Search on string