CODEWITHSUNDEEP
javaalgorithm
yu.pitomets
yu.pitomets

Reputation: 1840

Data structure to check if multiple periods overlap

I have a class Period that is represented by start and end dates, where end is after start. I need to write a function to check if periods overlap.

The straightforward approach is to check every period with every other period. Is there a way to introduce a data structure that will perform faster?

class Period {
      LocalDateTime start;
      LocalDateTime end;
}
 

boolean isOverlap(Set<Period> periods) {
    // TODO put the code here
}

isOverlap should return true when at least two of the periods overlap.

Upvotes: 1

Views: 243

Answers (1)

Mureinik
Mureinik

Reputation: 311853

Checking every period against every other period will have an O(n2) time complexity. Instead, I'd sort them by start and end times and then iterate over the list. This way, a period can only overlap the periods directly before and after it (or multiple subsequent ones before or after it - but that's inconsequential, since you're looking for a single overlap to return true). You can iterate over the list and check this. The total cost of this algorithm would be the cost of the sorting, O(nlog(n)):

boolean isOverlap(Set<Period> periods) {
    List<Period> sorted =
        periods.stream()
               .sorted(Comparator.comparing((Period p) -> p.start)
                                 .thenComparing(p -> p.end))
               .collect(Collectors.toList());
    for (int i = 0; i < sorted.size() - 1; ++i) {
        if (sorted.get(i).end.compareTo(sorted.get(i + 1).start) > 0) {
            return true;
        }
    }
    return false;
}

Upvotes: 3

Related Questions