Sweep Line (Intervals)
56. Merge Intervals
Given a collection of intervals, merge all overlapping intervals.
For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18].
class Solution {
public:
vector<Interval> merge(vector<Interval>& intervals) {
size_t len = intervals.size();
vector<Interval> res;
if (!len) return res;
sort(intervals.begin(), intervals.end(), [](Interval& a, Interval& b){return a.start < b.start;});
int start = intervals[0].start;
int end = intervals[0].end;
for (size_t i = 0; i < len; ++i) {
if(intervals[i].start <= end) {
end = max(intervals[i].end, end);
} else {
res.push_back({start, end});
start = intervals[i].start;
end = intervals[i].end;
}
}
res.push_back({start, end});
return res;
}
};
57. Insert Interval
Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).
You may assume that the intervals were initially sorted according to their start times.
Example 1: Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9]. Example 2: Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16]. This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].
class Solution {
public:
vector<Interval> insert(vector<Interval>& intervals, Interval newInterval) {
size_t len = intervals.size();
vector<Interval> res;
if (!len) return {newInterval};
size_t i = 0;
for (; i < len; ++i) {
if (intervals[i].end < newInterval.start) {
res.push_back(intervals[i]);
} else if (intervals[i].start <= newInterval.end){
newInterval.start = min(newInterval.start, intervals[i].start);
newInterval.end = max(newInterval.end, intervals[i].end);
} else break;
}
res.push_back(newInterval);
for (;i < len; ++i) res.push_back(intervals[i]);
return res;
}
};
252 meeting rooms
Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return false.
class Solution {
public:
bool canAttendMeetings(vector<Interval>& intervals) {
auto is_less = [](Interval& a, Interval&b) {return a.start < b.start;};
sort(intervals.begin(), intervals.end(), is_less);
for (size_t i = 1; i < intervals.size(); i++) {
if (intervals[i].start < intervals[i-1].end) return false;
}
return true;
}
};
128. Longest Consecutive Sequence
Given an unsorted array of integers, find the length of the longest consecutive elements sequence.
For example, Given [100, 4, 200, 1, 3, 2], The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.
Your algorithm should run in O(n) complexity.
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
unordered_set<int> sets(nums.begin(), nums.end());
int max_len = 0;
for (auto n : nums) {
if (sets.find(n) == sets.end()) continue;
int i = n - 1;
int j = n + 1;
while (sets.find(i) != sets.end()) sets.erase(i--);
while (sets.find(j) != sets.end()) sets.erase(j++);
int cur_len = j - i - 1;
max_len = max(cur_len, max_len);
}
return max_len;
}
};
163 Missing Ranges
Given a sorted integer array where the range of elements are [lower, upper] inclusive, return its missing ranges.
For example, given [0, 1, 3, 50, 75], lower = 0 and upper = 99, return ["2", "4->49", "51->74", "76->99"].
class Solution {
public:
vector<string> findMissingRanges(vector<int>& nums, int lower, int upper) {
vector<string> res;
size_t len = nums.size();
int start = lower;
int end = lower;
if (!len) return {genRange(lower, upper)};
for (size_t i = 0; i < len; ++i) {
if (nums[i] != start) {
end = nums[i] - 1;
res.push_back(genRange(start, end));
}
start = nums[i] + 1;
}
if (start != upper + 1) res.push_back(genRange(start, upper));
return res;
}
string genRange(int start, int end) {
string res = to_string(start);
if (start != end) res += "->" + to_string(end);
return res;
}
};
228. Summary Ranges
Given a sorted integer array without duplicates, return the summary of its ranges.
For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"].
class Solution {
public:
vector<string> summaryRanges(vector<int>& nums) {
vector<string> res;
size_t len = nums.size();
if (!len) return res;
int start = nums[0];
int end = nums[0];
for (size_t i = 0; i < nums.size(); ++i) {
if (end != nums[i]) {
res.push_back(genSummary(start, end - 1));
start = nums[i];
}
end = nums[i] + 1;
}
res.push_back(genSummary(start, end - 1));
return res;
}
string genSummary(int start, int end) {
string res = to_string(start);
if (start != end) res += "->" + to_string(end);
return res;
}
};
352. Data Stream as Disjoint Intervals
Given a data stream input of non-negative integers a1, a2, ..., an, ..., summarize the numbers seen so far as a list of disjoint intervals.
For example, suppose the integers from the data stream are 1, 3, 7, 2, 6, ..., then the summary will be:
[1, 1] [1, 1], [3, 3] [1, 1], [3, 3], [7, 7] [1, 3], [7, 7] [1, 3], [6, 7]Follow up: What if there are lots of merges and the number of disjoint intervals are small compared to the data stream's size?
/**
* Definition for an interval.
* struct Interval {
* int start;
* int end;
* Interval() : start(0), end(0) {}
* Interval(int s, int e) : start(s), end(e) {}
* };
*/
class SummaryRanges {
public:
/** Initialize your data structure here. */
SummaryRanges() {
}
void addNum(int val) {
auto it = intervals.lower_bound(Interval(val, val));
if (it != intervals.begin() && (--it)->end + 1< val) ++it;
int start = val, end = val;
while (it != intervals.end() && val + 1 >= it->start && val - 1 <= it->end) {
start = min(it->start, start);
end = max(it->end, end);
it = intervals.erase(it);
}
intervals.insert(Interval(start, end));
}
vector<Interval> getIntervals() {
vector<Interval> res;
for (auto it : intervals) res.push_back(it);
return res;
}
private:
struct cmp {
bool operator()(Interval a, Interval b) {
return a.start < b.start;
}
};
set<Interval, cmp> intervals;
};
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges obj = new SummaryRanges();
* obj.addNum(val);
* vector<Interval> param_2 = obj.getIntervals();
*/
The interval covering problem
you are given a set of closed intervals. Design an efficient algorithm for finding a minimum sized set of numbers that cover all the intervals
Greedy algorithm:
intuition: focus on extreme points. at the time we must have a point: when a line ends ==> sort based on right end.
vector<int> FindMinimumVisits(vector<Interval> intervals) {
if (intervals.empty()) {
return {};
}
// Sort intervals based on the right endpoints.
sort(intervals.begin(), intervals.end(),
[](const Interval& a, const Interval& b) -> bool {
return a.right < b.right;
});
vector<int> visits;
int last_visit_time = intervals.front().right;
visits.emplace_back(last_visit_time);
for (const Interval& interval : intervals) {
if (interval.left > last_visit_time) {
// The current right endpoint, last_visit_time, will not cover any more
// intervals.
last_visit_time = interval.right;
visits.emplace_back(last_visit_time);
}
}
return visits;
}
The view from above (EPI P426)
sweep line + BST
struct LineSegment {
int left, right; // Specifies the interval.
int color;
int height;
};
class Endpoint {
public:
bool operator<(const Endpoint& that) const {
return Value() < that.Value();
}
int Value() const { return isLeft_ ? line_->left : line_->right; }
bool isLeft_;
const LineSegment* line_;
};
vector<LineSegment> CalculateViewFromAbove(const vector<LineSegment>& A) {
vector<Endpoint> sorted_endpoints;
for (const LineSegment& a : A) {
sorted_endpoints.emplace_back(Endpoint{true, &a});
sorted_endpoints.emplace_back(Endpoint{false, &a});
}
sort(sorted_endpoints.begin(), sorted_endpoints.end());
vector<LineSegment> result;
int prev_xaxis = sorted_endpoints.front().Value(); // Leftmost end point.
unique_ptr<LineSegment> prev = nullptr;
map<int, const LineSegment*> active_line_segments;
for (const Endpoint& endpoint : sorted_endpoints) {
if (!active_line_segments.empty() && prev_xaxis != endpoint.Value()) {
if (prev == nullptr) { // Found first segment.
prev = make_unique<LineSegment>(
LineSegment{prev_xaxis, endpoint.Value(),
active_line_segments.crbegin()->second->color,
active_line_segments.crbegin()->second->height});
} else {
if (prev->height == active_line_segments.crbegin()->second->height &&
prev->color == active_line_segments.crbegin()->second->color &&
prev_xaxis == prev->right) {
prev->right = endpoint.Value();
} else {
result.emplace_back(*prev);
*prev = {prev_xaxis, endpoint.Value(),
active_line_segments.crbegin()->second->color,
active_line_segments.crbegin()->second->height};
}
}
}
prev_xaxis = endpoint.Value();
if (endpoint.isLeft_ == true) { // Left end point.
active_line_segments.emplace(endpoint.line_->height, endpoint.line_);
} else { // Right end point.
active_line_segments.erase(endpoint.line_->height);
}
}
// Output the remaining segment (if any).
if (prev) {
result.emplace_back(*prev);
}
return result;
}