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

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