Understanding the Main Question

Dates can be given as number-of-days, beginning from the first of January 1970. Epoch means 1st of January 1970. In this document, dates are given like that, by days, but with small numbers. Consider the following set of date pairs, consisting of startDate and endDate pairs:

    {(1, 5), (10, 15), (3, 7), (12, 18)}

Each pair is a time-span.

The startDate for the first given pair is 1. The enddate for this first given pair is 5.
The startDate for the second given pair is 10. The enddate for this second given pair is 15.
The startDate for the third given pair is 3. The enddate for this third given pair is 7.
The startDate for the fourth given pair is 12. The enddate for this fourth given pair is 18.

What is the pair with the longest time-span? - It is the pair, (12,18) because 18-12 = 6, while 5-1=4; 15-10=5; and 7-3=4.

Is 6 the longest duration? - If these pairs are placed on a (number) line, will there be any overlapping of the different spans of times? - In order to know the longest time-span for any duration, for the whole set of time (duration) pairs, overlapping of some endDates and the following startDates have to be considered.

The best way to know if there are any overlappings of some given durations (time pairs) is to sort (ascending) the pairs first. Pairs can be sorted by startDates or by endDates. It makes sense to sort the pairs by startDates. If the above pairs are sorted by startDates, then the following set, ordered by startdates, will result:

    { (1, 5), (3, 7), (10, 15), (12, 18) }

Each startDate has been displaced within the whole set, accompanied by its endDate. That is, the pairs have been displaced around, within the whole set, based on the startdate.

Observed from the whole set, that the complete range of durations, starts at day 1 and ends at day 18. However, it is not necessarily that whole range of time that is asked for. Within that complete range, the longest duration is asked for, taking into consideration any overleaping of some end and next start days.

It must be borne in mind that there are some possible time gaps within the whole complete range. The longest of the durations within consecutive time gaps, is what is asked for.

Manual-Run-Through of Duration Pairs (Intervals)

Notice from the first two given pairs, that the first given duration (interval) starts at day 1 and ends at day 5, while the second given pair starts at day 3 and ends at day 7. There is overlapping here, giving a longer duration of 7-1 = 6 days.

Notice from the second and third given pairs, that the second given pair ends at day 7 and the third given pair starts at day 10. There is a time gap here (no overlapping). So the longest time-span so far, is 6 days, from day 1 to day 7, consisting of the first and second given duration (interval) pairs, with an overlap.

Notice from the third and (last) fourth given pairs, that the third given duration starts at day 10 and ends at day 15, while the fourth given pair starts at day 12 and ends at day 18. There is overlapping here, giving a longer duration of 18-10 = 8 days. The longest time-span so far is 8 days, longer than the previous 6 days.

The list of pairs in the whole set, has been exhausted. The search for the longest time-span should end here, with the longest time-span of 8 days.

Algorithm

- Create an object of objects, where the principal object is the whole given set, and the sub-objects are the given duration pairs.
- Sort the sub-objects (pairs) by startDate.
- Scan linearly, the sorted list of pairs, looking for overlappings and gaps as illustrated in the above manual-run-through.

The Program

The program using the above sample pairs and whole set (principal object) is (read the code and comments):

import functools

# Structure to represent an interval
class Interval:
    def __init__(self, start, end):
        self.start = start
        self.end = end

# Function to calculate maximum timespan covered
def max_timespan(arr):
    # n is number of subsets (pairs)
    if arr is None or len(arr) == 0:
        return 0
    
    # Sort intervals based on Start Time - O(N log N)
    arr.sort(key=lambda x: x.start)
    
    max_span = 0
    actual_start_date = arr[0].start
    actual_end_date = arr[0].end
    
    # Linear scan to merge intervals - O(N)
    for i in range(1, len(arr)):
        # If current interval overlaps or is contiguous with active range
        if arr[i].start <= actual_end_date:
            if arr[i].end > actual_end_date:
                actual_end_date = arr[i].end  # Extend the current range
        else:
            # No overlap, calculate span of previous, update max
            current_span = actual_end_date - actual_start_date
            if current_span > max_span:
                max_span = current_span
                
            # Move to next range
            actual_start_date = arr[i].start
            actual_end_date = arr[i].end
            
    # Final check for the last interval group
    final_span = actual_end_date - actual_start_date
    if final_span > max_span:
        max_span = final_span
        
    return max_span

# Main function
# Using Python list of Interval objects
intervals = [
    Interval(1, 5),
    Interval(10, 15),
    Interval(3, 7),
    Interval(12, 18)
]
    
result = max_timespan(intervals)
print(f"Longest timespan covered: {result}")

The output is:

    Longest timespan covered: 8

Time Complexity

Sorting intervals by their start date takes O(N.log₂N) time.
Merging and calculating the max timespan requires one pass through the sorted intervals, taking O(N) time.
Complete time complexity is O(N.log₂N + N).