Posts published in “Geometry”

花花酱 LeetCode 759. Employee Free Time

By zxi on January 8, 2018

题目大意：给你每个员工的日历，让你找出所有员工都有空的时间段。

Problem:

We are given a list schedule of employees, which represents the working time for each employee.

Each employee has a list of non-overlapping Intervals, and these intervals are in sorted order.

Return the list of finite intervals representing common, positive-length free time for all employees, also in sorted order.

Example 1:

Input: schedule = [[[1,2],[5,6]],[[1,3]],[[4,10]]]

Output: [[3,4]]

Explanation:

There are a total of three employees, and all common

free time intervals would be [-inf, 1], [3, 4], [10, inf].

We discard any intervals that contain inf as they aren't finite.

Example 2:

1 2	Input: schedule = [[[1,3],[6,7]],[[2,4]],[[2,5],[9,12]]] Output: [[5,6],[7,9]]

(Even though we are representing Intervals in the form [x, y], the objects inside are Intervals, not lists or arrays. For example, schedule[0][0].start = 1, schedule[0][0].end = 2, and schedule[0][0][0] is not defined.)

Also, we wouldn’t include intervals like [5, 5] in our answer, as they have zero length.

Note:

schedule and schedule[i] are lists with lengths in range [1, 50].
0 <= schedule[i].start < schedule[i].end <= 10^8.

Idea:

Merge Intervals (virtually)

Solution:

C++

Time complexity: O(nlogn)

Space complexity: O(n)

n is the total number of intervals, n <= 2500

// Author: Huahua

// Running time: 81 ms

class Solution {

public:

vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {

vector<Interval> all;

for (const auto intervals : schedule)

all.insert(all.end(), intervals.begin(), intervals.end());

std::sort(all.begin(), all.end(),

[](const Interval& a, const Interval& b){

return a.start < b.start;

});

vector<Interval> ans;

int end = all.front().end;

for (const Interval& busy : all) {

if (busy.start > end)

ans.emplace_back(end, busy.start);

end = max(end, busy.end);

}

return ans;

}

};

Related Problems:

花花酱 LeetCode 732. My Calendar III

By zxi on December 6, 2017

Problem:

link: https://leetcode.com/problems/my-calendar-iii/description/

Implement a MyCalendarThree class to store your events. A new event can always be added.

Your class will have one 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 K-booking happens when K events have some non-empty intersection (ie., there is some time that is common to all K events.)

For each call to the method MyCalendar.book, return an integer K representing the largest integer such that there exists a K-booking in the calendar.

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

Example 1:

MyCalendarThree();
MyCalendarThree.book(10, 20); // returns 1
MyCalendarThree.book(50, 60); // returns 1
MyCalendarThree.book(10, 40); // returns 2
MyCalendarThree.book(5, 15); // returns 3
MyCalendarThree.book(5, 10); // returns 3
MyCalendarThree.book(25, 55); // returns 3
Explanation: 
The first two events can be booked and are disjoint, so the maximum K-booking is a 1-booking.
The third event [10, 40) intersects the first event, and the maximum K-booking is a 2-booking.
The remaining events cause the maximum K-booking to be only a 3-booking.
Note that the last event locally causes a 2-booking, but the answer is still 3 because
eg. [10, 20), [10, 40), and [5, 15) are still triple booked.

Note:

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

Idea:

Similar to LeetCode 731 My Calendar II Use an ordered / tree map to track the number of event at current time.

For a new book event, increase the number of events at start, decrease the number of events at end.

Scan the timeline to find the maximum number of events.

Solution 1: Count Boundaries

Time complexity: O(n^2)

Space complexity: O(n)

C++

// Author: Huahua

// Runtime: 116 ms

class MyCalendarThree {

public:

MyCalendarThree() {}

int book(int start, int end) {

++deltas_[start];

--deltas_[end];

int ans = 0;

int curr = 0;

for (const auto& kv : deltas_)

ans = max(ans, curr += kv.second);

return ans;

}

private:

map<int, int> deltas_;

};

Solution 2

C++

// Author: Huahua

// Runtime: 66 ms

class MyCalendarThree {

public:

MyCalendarThree() {

counts_[INT_MIN] = 0;

counts_[INT_MAX] = 0;

max_count_ = 0;

}

int book(int start, int end) {

auto l = prev(counts_.upper_bound(start)); // l->first < start

auto r = counts_.lower_bound(end); // r->first >= end

for (auto curr = l, next = curr; curr != r; curr = next) {

++next;

if (next->first > end)

counts_[end] = curr->second;

if (curr->first <= start && next->first > start)

max_count_ = max(max_count_, counts_[start] = curr->second + 1);

else

max_count_ = max(max_count_, ++curr->second);

}

return max_count_;

}

private:

map<int, int> counts_;

int max_count_;

};

Solution 3: Segment Tree

C++

// Author: Huahua

// Runtime: 63 ms (<95.65%)

class MyCalendarThree {

public:

MyCalendarThree(): max_count_(0) {

root_.reset(new Node(0, 100000000, 0));

}

int book(int start, int end) {

Add(start, end, root_.get());

return max_count_;

}

private:

struct Node {

Node(int l, int r, int count):l(l), m(-1), r(r), count(count){}

int l;

int m;

int r;

int count;

std::unique_ptr<Node> left;

std::unique_ptr<Node> right;

};

void Add(int start, int end, Node* root) {

if (root->m != -1) {

if (end <= root->m)

Add(start, end, root->left.get());

else if(start >= root->m)

Add(start, end, root->right.get());

else {

Add(start, root->m, root->left.get());

Add(root->m, end, root->right.get());

}

return;

}

if (start == root->l && end == root->r)

max_count_ = max(max_count_, ++root->count);

else if (start == root->l) {

root->m = end;

root->left.reset(new Node(start, root->m, root->count + 1));

root->right.reset(new Node(root->m, root->r, root->count));

max_count_ = max(max_count_, root->count + 1);

} else if(end == root->r) {

root->m = start;

root->left.reset(new Node(root->l, root->m, root->count));

root->right.reset(new Node(root->m, root->r, root->count + 1));

max_count_ = max(max_count_, root->count + 1);

} else {

root->m = start;

root->left.reset(new Node(root->l, root->m, root->count));

root->right.reset(new Node(root->m, root->r, root->count));

Add(start, end, root->right.get());

}

std::unique_ptr<Node> root_;

int max_count_;

};

Python3

"""

Author: Huahua

Runtime: 436 ms (<88.88%)

"""

class Node:

def __init__(self, l, r, count):

self.l = l

self.m = -1

self.r = r

self.count = count

self.left = None

self.right = None

class MyCalendarThree:

def __init__(self):

self.root = Node(0, 10**9, 0)

self.max = 0

def book(self, start, end):

self.add(start, end, self.root)

return self.max

def add(self, start, end, root):

if root.m != -1:

if end <= root.m: self.add(start, end, root.left)

elif start >= root.m: self.add(start, end, root.right)

else:

self.add(start, root.m, root.left)

self.add(root.m, end, root.right)

return

if start == root.l and end == root.r:

root.count += 1

self.max = max(self.max, root.count)

elif start == root.l:

root.m = end

root.left = Node(start, root.m, root.count + 1)

root.right = Node(root.m, root.r, root.count)

self.max = max(self.max, root.count + 1)

elif end == root.r:

root.m = start;

root.left = Node(root.l, root.m, root.count)

root.right = Node(root.m, root.r, root.count + 1)

self.max = max(self.max, root.count + 1)

else:

root.m = start

root.left = Node(root.l, root.m, root.count)

root.right = Node(root.m, root.r, root.count)

self.add(start, end, root.right)

Related Problems:

花花酱 LeetCode 731. My Calendar II – 花花酱

By zxi on November 19, 2017

Problem:

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

Your class will have one 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 triple booking happens when three events have some non-empty intersection (ie., there is some time that is common to all 3 events.)

For each call to the method MyCalendar.book, return true if the event can be added to the calendar successfully without causing a triple 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(50, 60); // returns true

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

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

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

MyCalendar.book(25, 55); // returns true

Explanation<b>:</b>

The first two events can be booked. The third event can be double booked.

The fourth event (5, 15) can't be booked, because it would result in a triple booking.

The fifth event (5, 10) can be booked, as it does not use time 10 which is already double booked.

The sixth event (25, 55) can be booked, as the time in [25, 40) will be double booked with the third event;

the time [40, 50) will be single booked, and the time [50, 55) will be double booked with the second event.

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:

Brute Force

Solution1:

Brute Force

Time Complexity: O(n^2)

Space Complexity: O(n)

// Author: Huahua

// Runtime: 82 ms

class MyCalendarTwo {

public:

MyCalendarTwo() {}

bool book(int start, int end) {

for (const auto& kv : overlaps_)

if (max(start, kv.first) < min(end, kv.second)) return false;

for (const auto& kv : booked_) {

const int ss = max(start, kv.first);

const int ee = min(end, kv.second);

if (ss < ee) overlaps_.emplace_back(ss, ee);

}

booked_.emplace_back(start, end);

return true;

}

private:

vector<pair<int, int>> booked_;

vector<pair<int, int>> overlaps_;

};

Java

// Author: Huahua

// Runtime: 156 ms

class MyCalendarTwo {

private List<int[]> booked_;

private List<int[]> overlaps_;

public MyCalendarTwo() {

booked_ = new ArrayList<>();

overlaps_ = new ArrayList<>();

}

public boolean book(int start, int end) {

for (int[] range : overlaps_)

if (Math.max(range[0], start) < Math.min(range[1], end))

return false;

for (int[] range : booked_) {

int ss = Math.max(range[0], start);

int ee = Math.min(range[1], end);

if (ss < ee) overlaps_.add(new int[]{ss, ee});

}

booked_.add(new int[]{start, end});

return true;

}

Python

"""

Author: Huahua

Runtime: 638 ms

"""

class MyCalendarTwo:

def __init__(self):

self.booked_ = []

self.overlaps_ = []

def book(self, start, end):

for s, e in self.overlaps_:

if start < e and end > s: return False

for s, e in self.booked_:

if start < e and end > s:

self.overlaps_.append([max(start, s), min(end, e)])

self.booked_.append([start, end])

return True

Solution 2:

Counting

Time Complexity: O(n^2logn)

Space Complexity: O(n)

// Author: Huahua

// Runtime: 212 ms

class MyCalendarTwo {

public:

MyCalendarTwo() {}

bool book(int start, int end) {

++delta_[start];

--delta_[end];

int count = 0;

for (const auto& kv : delta_) {

count += kv.second;

if (count == 3) {

--delta_[start];

++delta_[end];

return false;

}

if (kv.first > end) break;

}

return true;

}

private:

map<int, int> delta_;

};

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: