Posts tagged as “range”

花花酱 LeetCode 729. My Calendar I

By zxi on November 19, 2017

Problem:

Implement a MyCalendar class to store your events. A new event can be added if adding the event will not cause a double booking.

Your class will have the method, book(int start, int end). Formally, this represents a booking on the half open interval [start, end), the range of real numbers x such that start <= x < end.

A double booking happens when two events have some non-empty intersection (ie., there is some time that is common to both events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a double booking. Otherwise, return false and do not add the event to the calendar.

Your class will be called like this: MyCalendar cal = new MyCalendar(); MyCalendar.book(start, end)

Example 1:

MyCalendar();

MyCalendar.book(10, 20); // returns true

MyCalendar.book(15, 25); // returns false

MyCalendar.book(20, 30); // returns true

Explanation:

The first event can be booked. The second can't because time 15 is already booked by another event.

The third event can be booked, as the first event takes every time less than 20, but not including 20.

Note:

The number of calls to MyCalendar.book per test case will be at most 1000.
In calls to MyCalendar.book(start, end), start and end are integers in the range [0, 10^9].

Idea:

Binary Search

Solution1:

Brute Force: O(n^2)

C++

// Author: Huahua

// Runtime: 99 ms

class MyCalendar {

public:

MyCalendar() {}

bool book(int start, int end) {

for (const auto& event : booked_) {

int s = event.first;

int e = event.second;

if (max(s, start) < min(e, end)) return false;

}

booked_.emplace_back(start, end);

return true;

}

private:

vector<pair<int, int>> booked_;

};

Solution 2:

Binary Search O(nlogn)

C++

// Author: Huahua

// Runtime: 82 ms

class MyCalendar {

public:

MyCalendar() {}

bool book(int start, int end) {

auto it = booked_.lower_bound(start);

if (it != booked_.cend() && it->first < end)

return false;

if (it != booked_.cbegin() && (--it)->second > start)

return false;

booked_[start] = end;

return true;

}

private:

map<int, int> booked_;

};

Java

// Author: Huahua

// Runtime: 170 ms

class MyCalendar {

TreeMap<Integer, Integer> booked_;

public MyCalendar() {

booked_ = new TreeMap<>();

}

public boolean book(int start, int end) {

Integer lb = booked_.floorKey(start);

if (lb != null && booked_.get(lb) > start) return false;

Integer ub = booked_.ceilingKey(start);

if (ub != null && ub < end) return false;

booked_.put(start, end);

return true;

}

Related Problems:

花花酱 LeetCode 699. Falling Squares

By zxi on October 24, 2017

题目大意：方块落下后会堆叠在重叠的方块之上，问每一块方块落下之后最高的方块的高度是多少？

Problem:

On an infinite number line (x-axis), we drop given squares in the order they are given.

The i-th square dropped (positions[i] = (left, side_length)) is a square with the left-most point being positions[i][0] and sidelength positions[i][1].

The square is dropped with the bottom edge parallel to the number line, and from a higher height than all currently landed squares. We wait for each square to stick before dropping the next.

The squares are infinitely sticky on their bottom edge, and will remain fixed to any positive length surface they touch (either the number line or another square). Squares dropped adjacent to each other will not stick together prematurely.

Return a list ans of heights. Each height ans[i] represents the current highest height of any square we have dropped, after dropping squares represented by positions[0], positions[1], ..., positions[i].

Example 1:

Input: [[1, 2], [2, 3], [6, 1]]

Output: [2, 5, 5]

Explanation:

After the first drop of

positions[0] = [1, 2]:

_aa

-------

The maximum height of any square is 2.

After the second drop of

positions[1] = [2, 3]:

__aaa

_aa__

--------------

The maximum height of any square is 5.

The larger square stays on top of the smaller square despite where its center

of gravity is, because squares are infinitely sticky on their bottom edge.

After the third drop of

positions[1] = [6, 1]:

__aaa

_aa

_aa___a

--------------

The maximum height of any square is still 5.

Thus, we return an answer of

[2, 5, 5]

Example 2:

Input: [[100, 100], [200, 100]]

Output: [100, 100]

Explanation: Adjacent squares don't get stuck prematurely - only their bottom edge can stick to surfaces.

Note:

1 <= positions.length <= 1000.
1 <= positions[i][0] <= 10^8.
1 <= positions[i][1] <= 10^6.

Idea:

Range query with map

Solution:

C++ map

// Author: Huahua

// Runtime: 29 ms

class Solution {

public:

vector<int> fallingSquares(vector<pair<int, int>>& positions) {

vector<int> ans;

map<pair<int, int>, int> b; // {{start, end}, height}

int maxHeight = INT_MIN;

for (const auto& kv: positions) {

int start = kv.first;

int size = kv.second;

int end = start + size;

// first range intersect with new_interval

auto it = b.upper_bound({start, end});

if (it != b.begin()) {

auto it2 = it;

if ((--it2)->first.second > start) it = it2;

}

int baseHeight = 0;

vector<tuple<int, int, int>> ranges;

while (it != b.end() && it->first.first < end) {

const int s = it->first.first;

const int e = it->first.second;

const int h = it->second;

if (s < start) ranges.emplace_back(s, start, h);

if (e > end) ranges.emplace_back(end, e, h);

// max height of intesected ranges

baseHeight = max(baseHeight, h);

it = b.erase(it);

}

int newHeight = size + baseHeight;

b[{start, end}] = newHeight;

for (const auto& range: ranges)

b[{get<0>(range), get<1>(range)}] = get<2>(range);

maxHeight = max(maxHeight, newHeight);

ans.push_back(maxHeight);

}

return ans;

}

};

C++ vector without merge

// Author: Huahua

// Runtime: 46 ms

class Solution {

public:

vector<int> fallingSquares(vector<pair<int, int>>& positions) {

vector<int> ans;

vector<Interval> intervals;

int maxHeight = INT_MIN;

for (const auto& kv: positions) {

int start = kv.first;

int end = start + kv.second;

int baseHeight = 0;

for (const Interval& interval : intervals) {

if (interval.start >= end || interval.end <= start)

continue;

baseHeight = max(baseHeight, interval.height);

}

int height = kv.second + baseHeight;

intervals.push_back(Interval(start, end, height));

maxHeight = max(maxHeight, height);

ans.push_back(maxHeight);

}

return ans;

}

private:

struct Interval {

int start;

int end;

int height;

Interval(int start, int end, int height)

: start(start), end(end), height(height) {}

};

C++ / vector with merge (slower)

// Author: Huahua

// Runtime: 86 ms

class Solution {

public:

vector<int> fallingSquares(vector<pair<int, int>>& positions) {

vector<int> ans;

vector<Interval> intervals;

int maxHeight = INT_MIN;

for (const auto& kv: positions) {

vector<Interval> tmp;

int start = kv.first;

int end = start + kv.second;

int baseHeight = 0;

for (const Interval& interval : intervals) {

if (interval.start >= end || interval.end <= start) {

tmp.push_back(interval);

continue;

}

baseHeight = max(baseHeight, interval.height);

if (interval.start < start || interval.end > end)

tmp.push_back(interval);

}

int height = kv.second + baseHeight;

tmp.push_back(Interval(start, end, height));

intervals.swap(tmp);

maxHeight = max(maxHeight, height);

ans.push_back(maxHeight);

}

return ans;

}

private:

struct Interval {

int start;

int end;

int height;

Interval(int start, int end, int height)

: start(start), end(end), height(height) {}

};

Related Problems:

[解题报告] LeetCode 715. Range Module
[解题报告] LeetCode 218. The Skyline Problem
[解题报告] LeetCode 57. Insert Interval

花花酱 LeetCode 715. Range Module

By zxi on October 22, 2017

Problem:

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.

Idea:

map / ordered ranges

Solution:

C++ / vector

// Author: Huahua

// Runtime: 276 ms

class RangeModule {

public:

RangeModule() {}

void addRange(int left, int right) {

vector<pair<int, int>> new_ranges;

bool inserted = false;

for (const auto& kv : ranges_) {

if (kv.first > right && !inserted) {

new_ranges.emplace_back(left, right);

inserted = true;

}

if (kv.second < left || kv.first > right) {

new_ranges.push_back(kv);

} else {

left = min(left, kv.first);

right = max(right, kv.second);

}

if (!inserted) new_ranges.emplace_back(left, right);

ranges_.swap(new_ranges);

}

bool queryRange(int left, int right) {

const int n = ranges_.size();

int l = 0;

int r = n - 1;

// Binary search

while (l <= r) {

int m = l + (r - l) / 2;

if (ranges_[m].second < left)

l = m + 1;

else if (ranges_[m].first > right)

r = m - 1;

else

return ranges_[m].first <= left && ranges_[m].second >= right;

}

return false;

}

void removeRange(int left, int right) {

vector<pair<int, int>> new_ranges;

for (const auto& kv : ranges_) {

if (kv.second <= left || kv.first >= right) {

new_ranges.push_back(kv);

} else {

if (kv.first < left)

new_ranges.emplace_back(kv.first, left);

if (kv.second > right)

new_ranges.emplace_back(right, kv.second);

}

ranges_.swap(new_ranges);

}

vector<pair<int, int>> ranges_;

};

C++ / map

// Author: Huahua

// Runtime: 199 ms

class RangeModule {

public:

RangeModule() {}

void addRange(int left, int right) {

IT l, r;

getOverlapRanges(left, right, l, r);

// At least one range overlapping with [left, right)

if (l != r) {

// Merge intervals into [left, right)

auto last = r; --last;

left = min(left, l->first);

right = max(right, last->second);

// Remove all overlapped ranges

ranges_.erase(l, r);

}

// Add a new/merged range

ranges_[left] = right;

}

bool queryRange(int left, int right) {

IT l, r;

getOverlapRanges(left, right, l, r);

// No overlapping range

if (l == r) return false;

return l->first <= left && l->second >= right;

}

void removeRange(int left, int right) {

IT l, r;

getOverlapRanges(left, right, l, r);

// No overlapping range

if (l == r) return;

auto last = r; --last;

int start = min(left, l->first);

int end = max(right, last->second);

// Delete overlapping ranges

ranges_.erase(l, r);

if (start < left) ranges_[start] = left;

if (end > right) ranges_[right] = end;

}

private:

typedef map<int, int>::iterator IT;

map<int, int> ranges_;

void getOverlapRanges(int left, int right, IT& l, IT& r) {

l = ranges_.upper_bound(left);

r = ranges_.upper_bound(right);

if (l != ranges_.begin())

if ((--l)->second < left) l++;

}

};

Related Problems: