Interval Overlap Finder

Data Structures Intervals Query

You are required to design and implement a data structure that efficiently manages a collection of intervals and supports the following operations:

  1. Add Interval: Insert an interval defined by a start and end point into the collection.

  2. Remove Interval: Delete a previously added interval from the collection (assume exact match for removal).

  3. Query Overlap: Given a query interval, return all intervals in the collection that overlap with this query interval. Two intervals overlap if they share at least one common point.

Requirements & Constraints:

  • The intervals are represented as pairs of integers (start, end) where start ≤ end.
  • Consider optimizing your data structure for scenarios with many intervals and frequent queries.
  • The operations (adding, removing, and querying) should ideally have better than O(n) performance per query if possible.
  • You may use any programming language and built-in data structure libraries, but consider how the underlying design would scale with a large number of intervals.

Example Scenario:

Suppose the following intervals are added to the collection:

  • [1, 5]
  • [10, 15]
  • [20, 25]

A query for overlapping intervals with the interval [12, 22] should return at least [10, 15] and [20, 25].

Develop a solution that provides a clear API for these operations, and include tests or examples demonstrating the functionality and efficiency of your implementation.

Good luck!