Range Module

class IntervalManager {
public:
    IntervalManager() {}
    
    void insertRange(int start, int end) {
        auto s = ranges.upper_bound({start, INT_MAX});
        auto e = ranges.upper_bound({end, INT_MAX});
        if (s != ranges.begin()) {
            s--;
            if (s->second < start) s++;
        }
        if (s != e) {
            start = min(start, s->first);
            end = max(end, (--e)->second);
            ranges.erase(s, ++e);
        }
        ranges.insert({start, end});
    }
    
    bool isRangePresent(int start, int end) {
        auto iter = ranges.upper_bound({start, INT_MAX});
        if (iter == ranges.begin() || (--iter)->second < end) return false;
        return true;
    }
    
    void deleteRange(int start, int end) {
        auto s = ranges.upper_bound({start, INT_MAX});
        auto e = ranges.upper_bound({end, INT_MAX});
        if (s != ranges.begin()) {
            s--;
            if (s->second < start) s++;
        }
        if (s == e) return;
        int low = min(start, s->first);
        int high = max(end, (--e)->second);
        ranges.erase(s, ++e);
        if (low < start) ranges.insert({low, start});
        if (high > end) ranges.insert({end, high});
    }
    
private:
    set<pair<int, int>> ranges;
};

The solution implements a Range Module using C++ which allows for efficient operations over intervals or ranges. Here is a concise summary of how the class IntervalManager operates:

• Constructor (IntervalManager): Initializes an instance of the IntervalManager class.

• Insertion of a Range (insertRange): Adds a new interval to the interval set ranges. If the new interval overlaps with existing intervals, merges them into a single, continuous interval. This merging process involves:

  1. Locating the correct positions in the set to start merging (using upper_bound).
  2. Adjusting the start and end points by comparing with existing intervals.
  3. Erasing overlapping intervals from the set.
  4. Inserting the newly formed merged interval.

• Checking for a Range (isRangePresent): Determines if a specific interval is completely present in the set. The method ensures:

  1. Finding the proper interval position (if any).
  2. Confirming the interval fully includes the queried range.

• Deletion of a Range (deleteRange): Removes or adjusts the specified interval from the set ranges. Similar to insertion, this method:

  1. Identifies and removes the exact or overlapping intervals.
  2. Retains non-overlapping parts of existing intervals by inserting them back into the set after the specified range is removed.

The class uses a set of pairs to manage ranges, where each pair is treated as an interval. Both insertRange and deleteRange employ the standard upper_bound method to find the relevant position in the set for merging or splitting intervals. The effective use of set operations ensures that all methods perform optimally in log-scale time complexity relative to the number of intervals present.

class IntervalManager {
    
    TreeSet<Interval> intervals;
    
    public IntervalManager() {
        intervals = new TreeSet<>();
    }
    
    public void insertRange(int start, int end) {
        Iterator<Interval> iterator = intervals
            .tailSet(new Interval(0, start))
            .iterator();
        while (iterator.hasNext()) {
            Interval current = iterator.next();
            if (end < current.left) {
                break;
            }
            start = Math.min(start, current.left);
            end = Math.max(end, current.right);
            iterator.remove();
        }
        intervals.add(new Interval(start, end));
    }
    
    public boolean isCovered(int start, int end) {
        Interval next = intervals.higher(new Interval(0, start));
        return (next != null && next.left <= start && end <= next.right);
    }
    
    public void deleteRange(int start, int end) {
        Iterator<Interval> iterator = intervals
            .tailSet(new Interval(0, start - 1))
            .iterator();
        ArrayList<Interval> toAdd = new ArrayList<>();
        while (iterator.hasNext()) {
            Interval current = iterator.next();
            if (end < current.left) {
                break;
            }
            if (current.left < start) {
                toAdd.add(new Interval(current.left, start));
            }
            if (end < current.right) {
                toAdd.add(new Interval(end, current.right));
            }
            iterator.remove();
        }
        for (Interval interval : toAdd) {
            intervals.add(interval);
        }
    }
}
    
class Interval implements Comparable<Interval> {
    
    int left;
    int right;
    
    public Interval(int left, int right) {
        this.left = left;
        this.right = right;
    }
    
    public int compareTo(Interval that) {
        if (this.right == that.right) {
            return this.left - that.left;
        }
        return this.right - that.right;
    }
}

The provided Java code defines a class IntervalManager designed to manage and manipulate intervals using a TreeSet. The IntervalManager includes methods to insert, check coverage, and delete ranges within these intervals. Here's a breakdown of its functionality:

• Initialization:

  • Initialize intervals as a TreeSet which holds interval objects. This uses custom sorting defined in the Interval class.

• Inserting a Range:

  • insertRange(int start, int end) inserts a new interval into the set. If this new interval overlaps with existing ones, it merges them into a single, continuous interval.
  • It iterates over intervals that might overlap using tailSet and iterator. Overlapping intervals are removed, and the new, merged interval is added.

• Checking if a Range is Covered:

  • isCovered(int start, int end) returns true if there exists a single interval that entirely covers the given range from start to end.
  • This is checked using the higher method on intervals to find the minimum interval that starts just after the given start.

• Deleting a Range:

  • deleteRange(int start, int end) handles removing or adjusting intervals that overlap with a specified range.
  • During iteration, if an interval is partially overlapped, it is split into new intervals reflecting the non-overlapped portions. These new intervals are saved in a list and later added back to the TreeSet.

• Interval Class:

  • This nested class represents an interval with a left and right boundary.
  • Implements the Comparable interface to define the natural order of intervals within the TreeSet, primarily ordered by the right boundary and secondarily by the left boundary.

This configuration enables efficient operations pertinent to managing intervals such as adding, checking, and removing ranges, which are crucial for systems needing dynamic interval management such as time slots or range querying systems. The use of a TreeSet optimizes these operations with logarithmic time complexity concerning the number of intervals.