Algorithms to Check If Any Two Intervals Overlap


Given a list of intervals denoted with (start, end), implement a function that returns true if none of these intervals overlap.

Definition of Intervals

A interval can be defined in C/C++ struct where two constructors can be used to initialize a interval.

1
2
3
4
5
6
struct Interval {
  int start;
  int end;
  Interval() : start(0), end(0) {}
  Interval(int s, int e) : start(s), end(e) {}
};
struct Interval {
  int start;
  int end;
  Interval() : start(0), end(0) {}
  Interval(int s, int e) : start(s), end(e) {}
};

Bruteforce Algorithm to Check If Any Two Intervals Overlap

We can iterate every possible pairs of intervals, and check if they overlap, this bruteforce approach runs at O(n^2) complexity.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        for (size_t i = 0; i < intervals.size(); ++ i) {
            for (size_t j = i + 1; j < intervals.size(); ++ j) {
                if (overlap(intervals[i], intervals[j])) {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool overlap(const Interval &a, const Interval &b) {
        return ((a.end > b.start) && (a.start <= b.start)) ||
                ((a.start < b.end) && (a.start >= b.start));
    }
};
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        for (size_t i = 0; i < intervals.size(); ++ i) {
            for (size_t j = i + 1; j < intervals.size(); ++ j) {
                if (overlap(intervals[i], intervals[j])) {
                    return false;
                }
            }
        }
        return true;
    }
    
    bool overlap(const Interval &a, const Interval &b) {
        return ((a.end > b.start) && (a.start <= b.start)) ||
                ((a.start < b.end) && (a.start >= b.start));
    }
};

The following is another way to check if two intervals overlapping:

overlapping-interval Algorithms to Check If Any Two Intervals Overlap algorithms c / c++ learn to code sorting

overlapping-interval

1
2
3
4
public static boolean overlap(int[] interval1, int[] interval2) {
    return (Math.min(interval1[1], interval2[1]) >
            Math.max(interval1[0], interval2[0]));
}
public static boolean overlap(int[] interval1, int[] interval2) {
    return (Math.min(interval1[1], interval2[1]) >
            Math.max(interval1[0], interval2[0]));
}

Sorting with O(nlogn)

However, if we sort the intervals in the ascending order of the start, then we can do an further check O(n) between every adjacent intervals to see if they overlap. The overall complexity is O(nlogn).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) {
            return a.start < b.start;
        });
        for (size_t i = 1; i < intervals.size(); ++ i) {
            if (intervals[i].start < intervals[i - 1].end) {
                return false;
            }
        }
        return true;
    }
};
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
        sort(intervals.begin(), intervals.end(), [](const Interval &a, const Interval &b) {
            return a.start < b.start;
        });
        for (size_t i = 1; i < intervals.size(); ++ i) {
            if (intervals[i].start < intervals[i - 1].end) {
                return false;
            }
        }
        return true;
    }
};

See also: Teaching Kids Programming – Algorithms to Check If Any Intervals Overlapping (Meeting Rooms)

–EOF (The Ultimate Computing & Technology Blog) —

GD Star Rating
loading...
424 words
Last Post: Set Mismatch - Find the Duplicate and Missing Number in Array
Next Post: Hunting Down The Mythical High-Quality Code

The Permanent URL is: Algorithms to Check If Any Two Intervals Overlap

Leave a Reply