problem0715

README

715. Range Module

题目

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:

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

解题思路

见程序注释

Documentation

Index

• type RangeModule
  • func Constructor() RangeModule
  • func (r *RangeModule) AddRange(left int, right int)
  • func (r *RangeModule) QueryRange(left int, right int) bool
  • func (r *RangeModule) RemoveRange(left int, right int)

Types

type RangeModule

type RangeModule struct {
	// contains filtered or unexported fields
}

RangeModule 记录了跟踪的范围

func Constructor

func Constructor() RangeModule

Constructor 返回新建的 RangeModule

func (*RangeModule) AddRange

func (r *RangeModule) AddRange(left int, right int)

AddRange 添加追踪的返回

func (*RangeModule) QueryRange

func (r *RangeModule) QueryRange(left int, right int) bool

QueryRange 返回 true 如果 [left, right) 全部都在追踪范围内

func (*RangeModule) RemoveRange

func (r *RangeModule) RemoveRange(left int, right int)

RemoveRange 从追踪范围中删除 [left,right)