715. Range Module

A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.

A half-open interval [left, right) denotes all the real numbers x where left <= x < right.

Implement the RangeModule class:

• RangeModule() Initializes the object of the data structure.
• void addRange(int left, int right) Adds the half-open interval [left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval [left, right) that are not already tracked.
• boolean queryRange(int left, int right) Returns true if every real number in the interval [left, right) is currently being tracked, and false otherwise.
• void removeRange(int left, int right) Stops tracking every real number currently being tracked in the half-open interval [left, right).
   

Example 1:

Input:
[“RangeModule”, “addRange”, “removeRange”, “queryRange”, “queryRange”, “queryRange”]
[[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output:
[null, null, null, true, false, true]
Explanation:
RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked)
rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Constraints:

• $1<=left<right<=10^9$
• At most $10^4$ calls will be made to addRange, queryRange, and removeRange.

From: LeetCode
Link: 715. Range Module

Solution:

Ideas:

• This solution uses dynamic arrays to manage interval merging efficiently.
• The complexity per operation is roughly linear, but fast enough for 10⁴ calls.
• Consider replacing the array-based approach with balanced trees for further optimization if needed.

Code:

typedef struct {
    int left;
    int right;
} Interval;

typedef struct {
    Interval* data;
    int size;
    int capacity;
} RangeModule;

RangeModule* rangeModuleCreate() {
    RangeModule* obj = malloc(sizeof(RangeModule));
    obj->capacity = 1000;
    obj->size = 0;
    obj->data = malloc(sizeof(Interval) * obj->capacity);
    return obj;
}

void resize(RangeModule* obj) {
    obj->capacity *= 2;
    obj->data = realloc(obj->data, sizeof(Interval) * obj->capacity);
}

int compare(const void* a, const void* b) {
    return ((Interval*)a)->left - ((Interval*)b)->left;
}

void rangeModuleAddRange(RangeModule* obj, int left, int right) {
    Interval* res = malloc(sizeof(Interval) * (obj->size + 1));
    int idx = 0, i = 0;

    while (i < obj->size && obj->data[i].right < left)
        res[idx++] = obj->data[i++];

    while (i < obj->size && obj->data[i].left <= right) {
        left = left < obj->data[i].left ? left : obj->data[i].left;
        right = right > obj->data[i].right ? right : obj->data[i].right;
        i++;
    }

    res[idx++] = (Interval){left, right};

    while (i < obj->size)
        res[idx++] = obj->data[i++];

    free(obj->data);
    obj->data = res;
    obj->size = idx;
}

bool rangeModuleQueryRange(RangeModule* obj, int left, int right) {
    for (int i = 0; i < obj->size; ++i) {
        if (obj->data[i].left <= left && right <= obj->data[i].right)
            return true;
    }
    return false;
}

void rangeModuleRemoveRange(RangeModule* obj, int left, int right) {
    Interval* res = malloc(sizeof(Interval) * (obj->size + 1));
    int idx = 0;

    for (int i = 0; i < obj->size; ++i) {
        if (obj->data[i].right <= left || obj->data[i].left >= right) {
            res[idx++] = obj->data[i];
        } else {
            if (obj->data[i].left < left)
                res[idx++] = (Interval){obj->data[i].left, left};
            if (obj->data[i].right > right)
                res[idx++] = (Interval){right, obj->data[i].right};
        }
    }

    free(obj->data);
    obj->data = res;
    obj->size = idx;
}

void rangeModuleFree(RangeModule* obj) {
    free(obj->data);
    free(obj);
}