Formatted question description: https://leetcode.ca/all/715.html

715. Range Module

Level

Hard

Description

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

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.
queryRange(int left, int right) Returns true if and only if every real number in the interval [left, right) is currently being tracked.
removeRange(int left, int right) Stops tracking every real number currently being tracked in the interval [left, right).

Example 1:

addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Note:

A half open interval [left, right) denotes all real numbers left <= x < right.
0 < left < right < 10^9 in all calls to addRange, queryRange, removeRange.
The total number of calls to addRange in a single test case is at most 1000.
The total number of calls to queryRange in a single test case is at most 5000.
The total number of calls to removeRange in a single test case is at most 1000.

Solution

Create a class Interval that represents intervals. Each object of Interval has data fields start and end that represents the start position and the end position. The intervals are compared according to start in ascending order and then according to end in ascending order.

In the class, maintain a tree set to store the intervals, where the intervals are sorted in ascending order.

For method addRange(int left, int right), loop over all the intervals in the tree set. If an interval has intersection with the new interval [left, right) (which means the two intervals can be merged into a new interval), then update left and right to a larger interval, and remove the current interval from the tree set. If the current interval’s start is greater than right, then break the loop. Add the new interval [left, right) (where the two values may be updated) to the tree set.

For method queryRange(int left, int right), find the previous interval of the current interval [left, right) using floor method. If the previous interval exists and it contains the current interval, return true. Otherwise, find the next interval of the current interval using ceiling method. If the next interval exists and it contains the current interval, return true. Otherwise, return false.

For method removeRange(int left, int right), loop over all the intervals in the tree set. If an interval has intersection with the removed interval [left, right) (which means the two intervals can be merged into a new interval), then remove the current interval from the tree set, and if there are existing intervals after removing the current interval, add the existing intervals to the tree set.

class RangeModule {
    TreeSet<Interval> set;

    public RangeModule() {
        set = new TreeSet<Interval>();
    }
    
    public void addRange(int left, int right) {
        TreeSet<Interval> prevSet = new TreeSet<Interval>(set);
        for (Interval interval : prevSet) {
            if (interval.end >= left && interval.start <= right) {
                left = Math.min(left, interval.start);
                right = Math.max(right, interval.end);
                set.remove(interval);
            } else if (interval.start > right)
                break;
        }
        set.add(new Interval(left, right));
    }
    
    public boolean queryRange(int left, int right) {
        Interval curr = new Interval(left, right);
        Interval prev = set.floor(curr);
        if (prev != null && prev.end >= right)
            return true;
        else {
            Interval next = set.ceiling(curr);
            if (next != null && next.start == left)
                return true;
            else
                return false;
        }
    }
    
    public void removeRange(int left, int right) {
        TreeSet<Interval> prevSet = new TreeSet<Interval>(set);
        for (Interval interval : prevSet) {
            if (interval.end >= left && interval.start <= right) {
                set.remove(interval);
                if (interval.start < left)
                    set.add(new Interval(interval.start, left));
                if (interval.end > right)
                    set.add(new Interval(right, interval.end));
            } else if (interval.start > right)
                break;
        }
    }
}

class Interval implements Comparable<Interval> {
    int start;
    int end;

    public Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }

    public int compareTo(Interval interval2) {
        if (this.start != interval2.start)
            return this.start - interval2.start;
        else
            return this.end - interval2.end;
    }

    public boolean equals(Object obj) {
        if (obj instanceof Interval) {
            Interval interval2 = (Interval) obj;
            return this.start == interval2.start && this.end == interval2.end;
        } else
            return false;
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */

############

class Node {
    Node left;
    Node right;
    int add;
    boolean v;
}

class SegmentTree {
    private Node root = new Node();

    public SegmentTree() {
    }

    public void modify(int left, int right, int v) {
        modify(left, right, v, 1, (int) 1e9, root);
    }

    public void modify(int left, int right, int v, int l, int r, Node node) {
        if (l >= left && r <= right) {
            node.v = v == 1;
            node.add = v;
            return;
        }
        pushdown(node);
        int mid = (l + r) >> 1;
        if (left <= mid) {
            modify(left, right, v, l, mid, node.left);
        }
        if (right > mid) {
            modify(left, right, v, mid + 1, r, node.right);
        }
        pushup(node);
    }

    public boolean query(int left, int right) {
        return query(left, right, 1, (int) 1e9, root);
    }

    public boolean query(int left, int right, int l, int r, Node node) {
        if (l >= left && r <= right) {
            return node.v;
        }
        pushdown(node);
        int mid = (l + r) >> 1;
        boolean v = true;
        if (left <= mid) {
            v = v && query(left, right, l, mid, node.left);
        }
        if (right > mid) {
            v = v && query(left, right, mid + 1, r, node.right);
        }
        return v;
    }

    public void pushup(Node node) {
        node.v = node.left != null && node.left.v && node.right != null && node.right.v;
    }

    public void pushdown(Node node) {
        if (node.left == null) {
            node.left = new Node();
        }
        if (node.right == null) {
            node.right = new Node();
        }
        if (node.add != 0) {
            node.left.add = node.add;
            node.right.add = node.add;
            node.left.v = node.add == 1;
            node.right.v = node.add == 1;
            node.add = 0;
        }
    }
}

class RangeModule {
    private SegmentTree tree = new SegmentTree();

    public RangeModule() {
    }

    public void addRange(int left, int right) {
        tree.modify(left, right - 1, 1);
    }

    public boolean queryRange(int left, int right) {
        return tree.query(left, right - 1);
    }

    public void removeRange(int left, int right) {
        tree.modify(left, right - 1, -1);
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */

// OJ: https://leetcode.com/problems/range-module/
// Time: 
//      RangeModule: O(1)
//      addRange: O(N)
//      queryRange: O(logN)
//      removeRange: O(N)
// Space: O(N)
class RangeModule {
    map<int, int> m;
public:
    RangeModule() {}
    void addRange(int left, int right) {
        auto it = m.lower_bound(left);
        if (it != begin(m) && prev(it)->second >= left) --it;
        if (it != end(m)) left = min(left, it->first);
        while (it != end(m) && it->first <= right) {
            if (it->second <= right) it = m.erase(it);
            else {
                right = it->second;
                it = m.erase(it);
                right = it->second;
                break;
            }
        }
        m[left] = right;
    }
    bool queryRange(int left, int right) {
        auto it = m.lower_bound(left);
        if (it != begin(m) && prev(it)->second > left) --it;
        if (it == end(m)) return false;
        return it->first <= left && it->second >= right;
    }
    void removeRange(int left, int right) {
        auto it = m.lower_bound(left);
        if (it != begin(m) && prev(it)->second > left) {
            --it;
            int r = it->second;
            it->second = left;
            if (right < r) {
                m[right] = r;
                return;
            }
            ++it;
        }
        while (it != end(m) && it->first < right) {
            if (it->second <= right) it = m.erase(it);
            else {
                int r = it->second;
                m.erase(it);
                m[right] = r;
                break;
            }
        }
    }
};

class Node:
    def __init__(self):
        self.left = None
        self.right = None
        self.add = 0
        self.v = False


class SegmentTree:
    def __init__(self):
        self.root = Node()

    def modify(self, left, right, v, l=1, r=int(1e9), node=None):
        if node is None:
            node = self.root
        if l >= left and r <= right:
            if v == 1:
                node.add = 1
                node.v = True
            else:
                node.add = -1
                node.v = False
            return
        self.pushdown(node)
        mid = (l + r) >> 1
        if left <= mid:
            self.modify(left, right, v, l, mid, node.left)
        if right > mid:
            self.modify(left, right, v, mid + 1, r, node.right)
        self.pushup(node)

    def query(self, left, right, l=1, r=int(1e9), node=None):
        if node is None:
            node = self.root
        if l >= left and r <= right:
            return node.v
        self.pushdown(node)
        mid = (l + r) >> 1
        v = True
        if left <= mid:
            v = v and self.query(left, right, l, mid, node.left)
        if right > mid:
            v = v and self.query(left, right, mid + 1, r, node.right)
        return v

    def pushup(self, node):
        node.v = bool(node.left and node.left.v and node.right and node.right.v)

    def pushdown(self, node):
        if node.left is None:
            node.left = Node()
        if node.right is None:
            node.right = Node()
        if node.add:
            node.left.add = node.right.add = node.add
            node.left.v = node.add == 1
            node.right.v = node.add == 1
            node.add = 0


class RangeModule:
    def __init__(self):
        self.tree = SegmentTree()

    def addRange(self, left: int, right: int) -> None:
        self.tree.modify(left, right - 1, 1)

    def queryRange(self, left: int, right: int) -> bool:
        return self.tree.query(left, right - 1)

    def removeRange(self, left: int, right: int) -> None:
        self.tree.modify(left, right - 1, -1)


# Your RangeModule object will be instantiated and called as such:
# obj = RangeModule()
# obj.addRange(left,right)
# param_2 = obj.queryRange(left,right)
# obj.removeRange(left,right)

const N int = 1e9

type node struct {
	lch   *node
	rch   *node
	added bool
	lazy  int
}

type segmentTree struct {
	root *node
}

func newSegmentTree() *segmentTree {
	return &segmentTree{
		root: new(node),
	}
}

func (t *segmentTree) update(n *node, l, r, i, j, x int) {
	if l >= i && r <= j {
		n.added = x == 1
		n.lazy = x
		return
	}
	t.pushdown(n)
	m := int(uint(l+r) >> 1)
	if i <= m {
		t.update(n.lch, l, m, i, j, x)
	}
	if j > m {
		t.update(n.rch, m+1, r, i, j, x)
	}
	t.pushup(n)
}

func (t *segmentTree) query(n *node, l, r, i, j int) bool {
	if l >= i && r <= j {
		return n.added
	}
	t.pushdown(n)
	v := true
	m := int(uint(l+r) >> 1)
	if i <= m {
		v = v && t.query(n.lch, l, m, i, j)
	}
	if j > m {
		v = v && t.query(n.rch, m+1, r, i, j)
	}
	return v
}

func (t *segmentTree) pushup(n *node) {
	n.added = n.lch.added && n.rch.added
}

func (t *segmentTree) pushdown(n *node) {
	if n.lch == nil {
		n.lch = new(node)
	}
	if n.rch == nil {
		n.rch = new(node)
	}
	if n.lazy != 0 {
		n.lch.added = n.lazy == 1
		n.rch.added = n.lazy == 1
		n.lch.lazy = n.lazy
		n.rch.lazy = n.lazy
		n.lazy = 0
	}
}

type RangeModule struct {
	t *segmentTree
}

func Constructor() RangeModule {
	return RangeModule{
		t: newSegmentTree(),
	}
}

func (this *RangeModule) AddRange(left int, right int) {
	this.t.update(this.t.root, 1, N, left, right-1, 1)
}

func (this *RangeModule) QueryRange(left int, right int) bool {
	return this.t.query(this.t.root, 1, N, left, right-1)
}

func (this *RangeModule) RemoveRange(left int, right int) {
	this.t.update(this.t.root, 1, N, left, right-1, -1)
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * obj := Constructor();
 * obj.AddRange(left,right);
 * param_2 := obj.QueryRange(left,right);
 * obj.RemoveRange(left,right);
 */

715 - Range Module

715. Range Module

Level

Description

Solution

All Problems

All Solutions

Welcome to Subscribe On Youtube

715. Range Module

Level

Description

Solution

All Problems

All Solutions