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):

#include 
#include     //for the qsort() function

// Structure to represent an interval (sub-object)
typedef struct {
    int start;
    int end;
} Interval;

// Comparison function to sort intervals by start time
int compareIntervals(const void* a, const void* b) {
    Interval* int1 = (Interval*)a;
    Interval* int2 = (Interval*)b;
    return int1->start - int2->start;
}

// Function to calculate maximum timespan covered
int MaxTimespan(Interval arr[], int n) {    //n is number of subsets (pairs)
    if (n <= 0) return 0;

    // Sort intervals based on StartDate - O(N log N)
    qsort(arr, n, sizeof(Interval), compareIntervals);

    int maxTimespan = 0;
    int actualStartDate = arr[0].start;
    int actualEndDate = arr[0].end;

    // Linear scan to merge intervals - O(N)
    for (int i = 1; i < n; i++) {
        // If current interval overlaps or is contiguous with active range
        if (arr[i].start <= actualEndDate) {
            if (arr[i].end > actualEndDate) {
                actualEndDate = arr[i].end; // Extend the current range
            }
        } else {
            // No overlap, calculate span of previous, move to next
            int currentSpan = actualEndDate - actualStartDate;
            if (currentSpan > maxTimespan) maxTimespan = currentSpan;

            actualStartDate = arr[i].start;
            actualEndDate = arr[i].end;
        }
    }

    // Final check for the last interval group (complete range of subsets)
    int finalSpan = actualEndDate - actualStartDate;
    if (finalSpan > maxTimespan) maxTimespan = finalSpan;

    return maxTimespan;
}

int main() {
    Interval intervals[] = {{1, 5}, {10, 15}, {3, 7}, {12, 18}};    //principal object is a set (complete range)
    int n = sizeof(intervals) / sizeof(intervals[0]);

    int result = MaxTimespan(intervals, n);
    printf("Longest timespan covered: %d\n", result);

    return 0;
}

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).