Count Integers in Intervals

• Data Structure: Use a List<int[]> to store all intervals as they are added.
• add(left, right):
  • Simply append the new interval [left, right] to the list.
• count():
  1. Check if the list of intervals is empty. If so, return 0.
  2. Create a copy of the interval list to avoid modifying the original.
  3. Sort the copied list of intervals based on their start points.
  4. Initialize a new list, mergedIntervals, to store the result of merging.
  5. Add the first interval from the sorted list to mergedIntervals.
  6. Iterate through the rest of the sorted intervals:
     • If the current interval overlaps with the last interval in mergedIntervals, merge them by updating the end point of the last interval.
     • Otherwise, the intervals are disjoint, so add the current interval to mergedIntervals.
  7. After iterating through all intervals, mergedIntervals will contain a set of disjoint intervals.
  8. Calculate the total count by summing the lengths (right - left + 1) of all intervals in mergedIntervals.

Data Structure

We use a java.util.List<int[]> to store the intervals. The add operation is trivial, but the count operation bears the computational load.

add(left, right)

This method simply adds a new integer array new int[]{left, right} to our list. Its complexity is O(1).

count()

This is where the core logic resides. To find the total number of unique integers, we must first resolve any overlaps. This is a classic 'Merge Intervals' problem.

1. First, we sort all the intervals in our list based on their starting points.
2. Then, we iterate through the sorted intervals and merge any that overlap.
3. An interval [s1, e1] overlaps with [s2, e2] if s2 <= e1 (assuming the list is sorted by start times).
4. The merged interval will have a start of s1 and an end of max(e1, e2).
5. After producing a new list of disjoint, merged intervals, we can calculate the total count by summing up the size of each interval (right - left + 1).

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4import java.util.LinkedList;5 6class CountIntervals {7    private List<int[]> intervals;8 9    public CountIntervals() {10        intervals = new ArrayList<>();11    }12 13    public void add(int left, int right) {14        intervals.add(new int[]{left, right});15    }16 17    public int count() {18        if (intervals.isEmpty()) {19            return 0;20        }21 22        // Sort intervals based on the start point23        Collections.sort(intervals, (a, b) -> Integer.compare(a[0], b[0]));24 25        LinkedList<int[]> merged = new LinkedList<>();26        for (int[] interval : intervals) {27            // if the list of merged intervals is empty or if the current28            // interval does not overlap with the previous, simply append it.29            if (merged.isEmpty() || merged.getLast()[1] < interval[0]) {30                merged.add(interval.clone()); // Use clone to avoid modifying original list if needed31            } else {32                // otherwise, there is overlap, so we merge the current and previous33                // intervals.34                merged.getLast()[1] = Math.max(merged.getLast()[1], interval[1]);35            }36        }37        38        // To optimize subsequent calls, we can replace the old list with the merged one.39        this.intervals = new ArrayList<>(merged);40 41        int totalCount = 0;42        for (int[] interval : merged) {43            totalCount += (interval[1] - interval[0] + 1);44        }45        return totalCount;46    }47}

• Data Structure: Use a TreeMap<Integer, Integer> to store disjoint intervals, mapping start points to end points. Maintain an integer count for the total size.
• CountIntervals():
  • Initialize an empty TreeMap and set count = 0.
• add(left, right):
  1. Define the interval to be added as [start, end], initially [left, right].
  2. Find all existing intervals in the TreeMap that overlap with [start, end].
  3. An efficient way to do this is to start with entry = map.floorEntry(end) and iterate backwards as long as the entry's interval overlaps with [start, end].
  4. For each overlapping interval [l, r] found:
     • Merge it by updating start = min(start, l) and end = max(end, r).
     • Remove the old interval [l, r] from the TreeMap.
     • Decrement the total count by the length of the removed interval (r - l + 1).
  5. After all merges are complete, insert the new, combined interval [start, end] into the TreeMap.
  6. Increment the total count by the length of this new interval (end - start + 1).
• count():
  • Simply return the pre-calculated count variable.

Data Structure

We use a TreeMap<Integer, Integer> to store the disjoint intervals, where the key is the interval's start and the value is its end. This keeps the intervals sorted by their start times. We also maintain an integer variable, count, to store the total number of integers covered by these intervals.

add(left, right)

This is the core of the algorithm. Instead of recalculating the total count from scratch, we update it incrementally. When adding [left, right]:

1. We identify all existing intervals in our TreeMap that overlap with [left, right].
2. An existing interval [l, r] overlaps with a new interval [new_l, new_r] if l <= new_r and r >= new_l.
3. We can find these overlapping intervals efficiently. We start by looking for an interval [l, r] where l <= right. The TreeMap.floorEntry(right) method is perfect for this.
4. We then iterate backwards, merging all overlapping intervals into one large interval. For each interval we merge, we remove it from the map and subtract its length from our running count.
5. Finally, we add the newly formed, larger interval to the map and add its length to count.

count()

Since we maintain the count variable with every add operation, this method simply returns the current value of count, making it an O(1) operation.

1import java.util.Map;2import java.util.TreeMap;3 4class CountIntervals {5    private TreeMap<Integer, Integer> intervals;6    private int count;7 8    public CountIntervals() {9        intervals = new TreeMap<>();10        count = 0;11    }12 13    public void add(int left, int right) {14        int start = left;15        int end = right;16 17        // Find an entry whose start is less than or equal to the new interval's end.18        Map.Entry<Integer, Integer> entry = intervals.floorEntry(end);19 20        // Iterate backwards through all intervals that overlap with the new one.21        while (entry != null && entry.getValue() >= start) {22            int l = entry.getKey();23            int r = entry.getValue();24 25            // Merge the overlapping interval with our new interval.26            start = Math.min(start, l);27            end = Math.max(end, r);28 29            // Remove the old interval and subtract its length from the total count.30            intervals.remove(l);31            this.count -= (r - l + 1);32 33            // Move to the previous entry to check for more overlaps.34            entry = intervals.floorEntry(start - 1);35        }36 37        // Add the new merged interval to the map and its length to the count.38        intervals.put(start, end);39        this.count += (end - start + 1);40    }41 42    public int count() {43        return this.count;44    }45}