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

package main

import (
	"fmt"
	"sort"
)

// Interval structure to represent a time range
type Interval struct {
	start int
	end   int
}

// Function to calculate maximum timespan covered
func maxTimespan(arr []Interval) int {
	if len(arr) == 0 {
		return 0
	}

	// Sort intervals based on Start Time - O(N log N)
	sort.Slice(arr, func(i, j int) bool {
		return arr[i].start < arr[j].start
	})

	maxSpan := 0
	actualStartDate := arr[0].start
	actualEndDate := arr[0].end

	// Linear scan to merge intervals - O(N)
	for i := 1; i < len(arr); 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, update max
			currentSpan := actualEndDate - actualStartDate
			if currentSpan > maxSpan {
				maxSpan = currentSpan
			}
			// Move to next range
			actualStartDate = arr[i].start
			actualEndDate = arr[i].end
		}
	}

	// Final check for the last interval group
	finalSpan := actualEndDate - actualStartDate
	if finalSpan > maxSpan {
		maxSpan = finalSpan
	}

	return maxSpan
}

func main() {
	// Using Go slice instead of vector
	intervals := []Interval{
		{1, 5},
		{10, 15},
		{3, 7},
		{12, 18},
	}
	result := maxTimespan(intervals)
	fmt.Printf("Longest timespan covered: %d\n", 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).