Count Integers in Intervals - Practice Coding Problems

Count Integers in Intervals - Problem

Given an empty set of intervals, implement a data structure that can:

Add an interval to the set of intervals
Count the number of integers that are present in at least one interval

Implement the CountIntervals class:

CountIntervals() Initializes the object with an empty set of intervals
void add(int left, int right) Adds the interval [left, right] to the set of intervals
int count() Returns the number of integers that are present in at least one interval

Note that an interval [left, right] denotes all the integers x where left <= x <= right.

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["CountIntervals", "add", "count", "add", "count"], values = [[], [2, 3], [], [4, 5], []]

› Output: [null, null, 2, null, 4]

💡 Note: Initialize empty intervals, add [2,3] (count=2), add [4,5] (count=4 total)

Example 2 — Overlapping Intervals

$ Input: operations = ["CountIntervals", "add", "add", "count"], values = [[], [2, 3], [4, 5], []]

› Output: [null, null, null, 4]

💡 Note: Add [2,3] and [4,5], total unique integers: 2,3,4,5 = 4 numbers

Example 3 — Merging Intervals

$ Input: operations = ["CountIntervals", "add", "add", "count"], values = [[], [1, 3], [2, 4], []]

› Output: [null, null, null, 4]

💡 Note: Intervals [1,3] and [2,4] overlap, merge to [1,4] covering 4 integers

Constraints

1 ≤ left ≤ right ≤ 10⁹
At most 10⁵ calls in total to add and count

Visualization

Tap to expand

Understanding the Visualization

Input Operations

Sequence of add() and count() operations on intervals

Merge Process

Overlapping intervals are merged to avoid double counting

Count Result

Return total unique integers covered by all intervals

Key Takeaway

🎯 Key Insight: Merge overlapping intervals to efficiently count unique integers without duplication

Asked in

G Google 25 a Amazon 18 M Microsoft 15

The key insight is to merge overlapping intervals to avoid double counting integers. The optimal approach uses efficient data structures like segment trees or ordered sets to handle interval merging in O(log n) time per operation. Best approach achieves O(n log n) time complexity and O(n) space complexity.

Common Approaches

Approach	Time	Space	Notes
✓ Store All Intervals Separately	O(n×R)	O(n + R)	Keep all intervals in a list and count unique integers each time
Merge Overlapping Intervals	O(n²)	O(n)	Merge overlapping intervals to avoid double counting

Store All Intervals Separately — Algorithm Steps

Store each new interval in a list
For count, iterate through all intervals
Use a set to track unique integers covered

Visualization

Tap to expand

Step-by-Step Walkthrough

Store Intervals

Add each interval to a list

Count All Numbers

Iterate through all intervals and count unique numbers

Return Count

Return total unique integers

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    int intervals[1000][2];
    int size;
} CountIntervals;

CountIntervals* countIntervalsCreate() {
    CountIntervals* obj = malloc(sizeof(CountIntervals));
    obj->size = 0;
    return obj;
}

void countIntervalsAdd(CountIntervals* obj, int left, int right) {
    obj->intervals[obj->size][0] = left;
    obj->intervals[obj->size][1] = right;
    obj->size++;
}

int countIntervalsCount(CountIntervals* obj) {
    int uniqueNums[10000] = {0};
    int count = 0;
    
    for (int i = 0; i < obj->size; i++) {
        for (int j = obj->intervals[i][0]; j <= obj->intervals[i][1]; j++) {
            if (j >= 0 && j < 10000 && !uniqueNums[j]) {
                uniqueNums[j] = 1;
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    printf("[null,null,0,null,4,null,6]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n×R)

n operations, each count takes O(R) where R is the total range size

✓ Linear Growth

Space Complexity

O(n + R)

Store n intervals plus O(R) space for counting unique integers

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Store All Intervals Separately — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler