Today I solved two problems on LeetCode that involved intervals(i.e., pairs of values of the form [start, end]) and I thought it would be a good idea to share a basic strategy that I know of for tackling these kinds of problems.

So, intervals are not difficult to understand, the idea is actually quite intuitive, but dealing with them can be a little tricky depending on the task at hand. Today I’ll show you how to solve problems like the following:

Given a collection of intervals of the form [start, end], which might overlap, return a new collection of non-overlapping intervals which is the result of merging the intervals provided as input. For instance:

Input: [1, 7], [4, 9], [9, 13]
Output: [1, 13]

If this example is not clear enough, please check out the practice problems at the end of this post for more details.

Algorithm

The algorithm consists of separating the intervals into events(start events and end events) and sorting them by value and breaking ties by type. For instance, using the example problem above, we would get the following events:

[
    {1, Start},
    {4, Start},
    {7, End},
    {9, Start},
    {9, End},
    {13, End}
]

As you can see, we have a tie, two intervals have the value 9, but we break the tie using the event type. In this problem, a Start event has higher priority than an End event.

Once we have the events sorted, we process them from left to right, keeping track of how many active segments we have at any given moment. There are cases that we have to handle:

• The counter transitioned from 0 to non-zero: we found the start of an interval
• The counter transitioned from non-zero to zero: we just found the end of the interval

That’s it. Now let’s see how it looks in code.

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
const int kStart = 1;
const int kEnd = 2;

struct Event {
    int time, type;
    Event() {}
    Event(int time, int type) : time(time), type(type) { }
    bool operator<(const Event& that) const {
        if (this->time != that.time) {
            return this->time < that.time;
        }
        return this->type < that.type;
    }
};

class Solution {
    public:
        vector<Interval> merge(vector<Interval>& intervals) {
            vector<Event> events;
            for (auto interval : intervals) {
                events.push_back({interval.start, kStart});
                events.push_back({interval.end, kEnd});
            }
            std::sort(events.begin(), events.end());
            int active = 0;
            vector<Interval> results;
            Interval interval;
            for (auto event : events) {
                if (event.type == kStart) {
                    active++;
                    if (active == 1) {
                        interval.start = event.time;
                    }
                } else {
                    active--;
                    if (active == 0) {
                        interval.end = event.time;
                        results.push_back(interval);
                    }
                }
            }
            return results;
        }
};

Notes

Of course this algorithm can’t be applied to all interval problems, you might have to adjust it a little bit or go with a completely different approach.

The complexity of this algorithm is O(N log N + N) which is simply O(N log N).

Practice problems

• Merge intervals
• Insert interval