Recently, I meet two different use cases related to interval:
define interval [start, end) as:
class Inteval {
int start, end;
}
First one, I need to design a data structrue which has following APIs:
void insert(Interval interval);
boolean contain(Interval interval);
void remove(Interval interval);
For example:
I insert [1,4), [3, 6), [9, 12), the internal interval is [1, 6), [9, 12).
If I call contain([2, 5)), it will return true, although there is no seperate interval which can cover [2, 5).
contain([4, 7)) return false
When I remove([10, 11)), the internal interval is [1, 6), [9, 10), [11, 12).
My Question: What is best data structure for above use case? (assume all APIs have the same call frequency)
Second one, I need to design a data structrue which has following APIs:
void insert(Interval interval);
boolean has(Interval interval);
boolean cover(Interval interval);
boolean remove(Interval interval);
For example:
I insert [1,4), [1, 4), [3, 6), [9, 12), the internal interval is [1,4), [1, 4), [3, 6), [9, 12), not [1, 6), [9, 12)(Interval will not merge with each other).
boolean has(Interval interval) means internal intervals have an exactly same one. has([1,4)), return true, has([1,2)), return false.
boolean cover(Interval interval) means there is at least one internal interval can fully cover, not the merge one.
boolean cover([2, 5)) return false, although merging [1, 4) and [3, 6) can cover [2, 5) but neither of them can seperately cover.
boolean cover([2, 3)) return true, cover([3, 4)) return true.
remove(Interval interval) can only remove exactly same interval.
remove([1, 3)) return false remove([1, 5)) return false remove([1, 4)) return true, then internal interval will be [1, 4),[3, 6), [9, 12).
My Question: What is best data structure for second use case? (assume all APIs have the same call frequency)