Non-Overlapping Intervals in C++: A Quantitative Developer Interview Question

In quantitative developer interviews, you’re often tested not just on algorithms, but on how they apply to real-world financial systems. One common scenario: cleaning overlapping time intervals from noisy market data feeds. This challenge maps directly to LeetCode 435: Non-Overlapping Intervals. In this article, we’ll solve it in C++ and explore why it matters in quant finance from ensuring data integrity to preparing time series for model training. How to solve the problem of non-overlapping intervals in C++?

Let’s dive into a practical problem that tests both coding skill and quant context.

1. Problem Statement

You’re given a list of intervals, where each interval represents a time range during which a market data feed was active. Some intervals may overlap, resulting in duplicated or conflicting data.

Your task is to determine the minimum number of intervals to remove so that the remaining intervals do not overlap. The goal is to produce a clean, non-overlapping timeline: a common requirement in financial data preprocessing.

Input: intervals = {{1,3}, {2,4}, {3,5}, {6,8}}
Output: 1

Explanation: Removing {2,4} results in non-overlapping intervals: {{1,3}, {3,5}, {6,8}}.

2. The Solution Explained

To remove the fewest intervals and eliminate overlaps, we take a greedy approach: we always keep the interval that ends earliest, since this leaves the most room for future intervals.

By sorting all intervals by their end time, we can iterate through them and:

• Keep an interval if it doesn’t overlap with the last selected one.
• Remove it otherwise.

This strategy ensures we keep as many non-overlapping intervals as possible and thus remove the minimum necessary.

What is the time and space complexity for this approach?

Sorting dominates the time complexity. While the actual iteration through the intervals is linear (O(n)), sorting the n intervals takes O(nlogn), and that becomes the bottleneck.

Although we process all n intervals, we do so in place without allocating any extra data structures. We use just a few variables (last_end, removed), so the auxiliary space remains constant. That’s why the space complexity is O(1) assuming the input list is already given and we’re allowed to sort it directly.

Now, let’s implement it in C++.

3. A C++ Implementation

Here is a C++ implementation of the solution:

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

// Greedy function to compute the minimum number of overlapping intervals to remove
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
    // Sort intervals by end time
    sort(intervals.begin(), intervals.end(), [](const auto& a, const auto& b) {
        return a[1] < b[1];
    });

    int removed = 0;
    int last_end = INT_MIN;

    for (const auto& interval : intervals) {
        if (interval[0] < last_end) {
            // Overlapping — must remov.e this one
            removed++;
        } else {
            // No overlap — update last_end
            last_end = interval[1];
        }
    }

    return removed;
}

int main() {
    vector<vector<int>> intervals = {{1, 3}, {2, 4}, {3, 5}, {6, 8}};
    int result = eraseOverlapIntervals(intervals);
    cout << "Minimum intervals to remove: " << result << endl;
    return 0;
}

Let’s compile:

mkdir build
cmake ..
make

And run the code:

➜  build git:(main) ✗ ./intervals
Minimum intervals to remove: 1

4. Do It Yourself

To do it yourself, you can clone my repository to solve non-overlapping intervals in C++here:

https://github.com/clemcrafts/overlappingintervals

Just git clone and run the compilation/execution commands from the Readme:

# Overlapping Intervals

The overlapping intervals problem for quant interviews.

## Build

```bash
mkdir build
cd build
cmake ..
make
```

## Run
```
./intervals