X5_Interval & Sliding Window

§Problem

Merge Intervals
- follow up
  
  list in java is not thread safe: synchronized
  
  concurrent list java
- note
  1. 先确认signature，再确认requirement
    work through test，画图说明
  2. compare的时候要用Integer.compare，而不是相减，会溢出
  3. collection.sort是modified merge sort（因为stable，保持相对顺序，eg. 1 2 2’ 3不会出现1 2’ 2 3）
    object use merge sort，primitive type use quick sort
  4. 用collections.emptyList()，是系统初始化好的，不用开辟额外的空间。如果用new Arraylist<>()会占新的空间
  5. Runtime, 要根据代码nlogn
  6. test case copy到代码附近
  7. 定义res时候直接最下面写return res。显得有条理
  8. 先定义cur，而不是每次a.get(i )，更清晰
- FB变种，raindrop
  
  rope 0-1, [0.2,0.5], [0.75,1.0], [0.3,0.75]
  1. deal with float
    private static final float EPSILON = 1e-10
    Math.abs(a-b) < EPSILON
  2. If drops are given on by one. Not all in the begining. -> 57. insert Interval
    
    boolean isWet, 0-1 all is wet
    
    注意处理边界，如果drop>1

Comparable vs Comparator in Java

// 定义在class内部
class Movie implements Comparable<Movie>{
  public int compareTo(Movie m){}
}
Collection.sort(list);

// 定义专门的compare函数
class RatingCompare implements Comparator<Movie>{
  pulic int compare(Movie m1, Movie m2){}
}
RatingCompare ratingCompare = new Rating Compare();
Collection.sort(list, ratingCompare);

Amazon OA Window Sum
给定数组，给定长度，算出数组里面，在这个长度下，分别的连续和
1
2
3
4
> Given array: [1,2,3,4,5,6,7]
> Given window: 3
> Output: [6,9,12,15,18]
>
Sliding Window

Hard: 689. Maximum Sum of 3 Non-Overlapping Subarrays

find 3, fixed subarray size = k => linear time

else , not linear time, different sol, is similar to the buy and sell stock problem.

1, 2, 1, 2, 6, 7, 5, 1
...........[s1  ].....
maxFromLeft      maxFromRight
       1, 2, 1, 2, 6, 7, 5, 1
presum:3, 3, 3, 8,13,12, 6 
maxFL: 0, 0, 0, 3, 4       <-index
       3, 3, 3, 8, 13      <-value
maxFR: 0, 0, 0, 0, 4, 5, 6 <-index
       ., ., ., .,13,12, 6 <-value
     
s1: [k, n-2k]; s0:[0,i-k]; s2:[i+k,n-1]
sum = presum[maxFromLeft[i - k]] + presum[i] + presum[maxFromRight[i + k]]

class Solution {
public:
    vector<int> maxSumOfThreeSubarrays(vector<int>& nums, int k) {
    	int n = nums.size();
    	vector<long> presum(n,0);
    	long sum = 0;
        for (int i = 0; i < n; ++i){
        	if (i>=k){
        		presum[i-k] = sum;
        		sum -= nums[i-k];
        	}
        	sum += nums[i];
        }
        presum[n-k] = sum;
        vector<int> maxFL(n,0), maxFR(n,0);
        sum = 0; int idx = 0;
        for (int i = 0; i <= n-3*k; ++i){
        	if (presum[i] > sum){
        		sum = presum[i];
        		idx = i;
        	}
        	maxFL[i] = idx;
        }
        sum = 0; idx = 0;
        for (int i = n-k; i >= 2*k; --i){
			if (presum[i] > sum){
        		sum = presum[i];
        		idx = i;
        	}
        	maxFR[i] = idx;
        }
        sum = 0; idx = 0;
        for (int i = k; i <= n-2*k; ++i){
        	long tmp = presum[maxFL[i-k]]+presum[i]+presum[maxFR[i+k]];
        	if (tmp > sum){
        		sum = tmp;
        		idx = i;
        	}
        }   
        return {maxFL[idx-k], idx, maxFR[idx+k]};
    }
};

Interfaces and Inheritance in Java

Interface inheitance: An Interface can extend other interface.

//Class: Smple —implements—> Interface: intFB —extends—>Interface: intFA
interface intFA{
  void geekName();
}
interface intFB extends intFA{
  void geekInstitute()
}
class sample implements intFB{
  @override
  public void geekName(){...}
  @override
  public void geekInstitute(){...}
}

Airbnb: 759. Employee Free Time

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:
1
2
3
4
5
6
7
8
> 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
3

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

//similar to 252, 253
class Solution {
public:
    vector<Interval> employeeFreeTime(vector<vector<Interval>>& schedule) {
    	vector<int> starts, ends;
    	for (auto s:schedule)
    		for (auto i:s){
	    		starts.push_back(i.start);
	    		ends.push_back(i.end);
    		}
    	sort(starts.begin(),starts.end());
    	sort(ends.begin(),ends.end());
    	vector<Interval> ans;
    	for (int i = 0; i < starts.size() - 1; ++i)
    		if (ends[i] < starts[i+1])
    			ans.push_back(Interval(ends[i],starts[i+1]));
    		// ==> starts[ends[i].index] < starts[i+1]
    		// ==> there is i starts and they have already ended
    		// ==> there is free interval x before next i+1 start
    	return ans; 
    }
};

56. Merge Intervals | Sort

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) {
        if (intervals.empty())
            return {};
        sort(intervals.begin(), intervals.end(), [](Interval a, Interval b){return a.start < b.start;});
        int end = intervals[0].end, beg = intervals[0].start;
        vector<Interval> ans;
        for (int i=1; i<intervals.size(); i++){
            if (intervals[i].start<=end)
                end = max(end,intervals[i].end);
            else {
                ans.push_back(Interval(beg,end));
                beg = intervals[i].start;
                end = intervals[i].end;
            }
            
        }
        if (beg!=-1)
            ans.push_back(Interval(beg,end));
        return ans;
    }
};

23. Merge k Sorted Lists

struct compare{
  bool operator()(const ListNode* l1, const ListNode* l2){
    return l1->val > l2->val;
  }
};
class Solution{
public:
  ListNode* mergeKLists(vector<ListNode*>& lists){
    priority_queue<ListNode*, vector<ListNode*>, compare> q;
    //for (ListNode* l:lists)
    for (auto l:lists)
      if (l)
        q.push(l);
    if (q.empty())
      return NULL;
    ListNode* ans = q.top();
    ListNode* h = ans;
    q.pop();
    if (h->next) q.push(h->next);
    while (!q.empty()){
      h->next = q.top();
      q.pop();
      h = h->next;
      if (h->next) q.push(h->next);
    }
    return ans;
  }
};

Or, binary use Merge2Lists

§Materials

Meeting Rooms II -Interval 所有题型总结归纳

683. K Empty Slots | sliding window

There is a garden with N slots. In each slot, there is a flower. The N flowers will bloom one by one in N days. In each day, there will be exactly one flower blooming and it will be in the status of blooming since then.

Given an array flowers consists of number from 1 to N. Each number in the array represents the place where the flower will open in that day.

For example, flowers[i] = x means that the unique flower that blooms at day i will be at position x, where i and x will be in the range from 1 to N.

Also given an integer k, you need to output in which day there exists two flowers in the status of blooming, and also the number of flowers between them is k and these flowers are not blooming.

If there isn’t such day, output -1.

Example 1:
1
2
3
4
5
6
> Input: 
> flowers: [1,3,2]
> k: 1
> Output: 2
> Explanation: In the second day, the first and the third flower have become blooming.
>

Example 2:

> Input: 
> flowers: [1,2,3]
> k: 1
> Output: -1
>

Note:

The given array will be in the range [1, 20000].

/*
flowers[i] = x : the unique flower that blooms at day i+1 will be at position x
=> day[x-1] = i+1

x1 = f[i], x2 = f[j], x1 < x2
sum( x1 < f[max(i,j)+1...N-1] < x2) == k
=>
sliding window
left = x, right = x+k+1
day[x+1]...day[x+k] > max(day[left],day[right])
*/
class Solution {
public:
    int kEmptySlots(vector<int>& flowers, int k) {
    	int ans = INT_MAX;
    	int n = flowers.size();
    	vector<int> days(n,0);
    	for (int i = 0; i < n; ++i)
    		days[flowers[i]-1] = i + 1;
    	int left = 0, right = k+1;
    	int day = max(days[left],days[right]);
    	for (int i = 1; right < n; ++i){
    		if (days[i] > day)
    			continue;
    		if (i == right) // find one
    			ans = min(ans,day);
    		left = i;
    		right = i+k+1;
    		day = max(days[left],days[right]);
    	}
    	return ans == INT_MAX ? -1 : ans;    
    }
};

252. Meeting Rooms | Sort

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.

/**
 * Definition for an interval.
 * struct Interval {
 *     int start;
 *     int end;
 *     Interval() : start(0), end(0) {}
 *     Interval(int s, int e) : start(s), end(e) {}
 * };
 */
// sort with start time, itv[i].end>itc[i+1].start -> overloap
class Solution {
public:
    bool canAttendMeetings(vector<Interval>& intervals) {
    	int n = intervals.size();
    	if (n == 0)
    		return true;
    	auto comp = [](Interval& a, Interval& b){
    		return a.start < b.start;
    	};
    	sort(intervals.begin(),intervals.end(),comp);
        for (int i = 0; i < n-1; ++i)
        	if (intervals[i].end > intervals[i+1].start)
        		return false;
        return true;
    }
};

253. Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.

For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.

/*
sort with start & sort with end
i, j <= i
if si < ej <=> i==j | when i comes, j is not end
=> overlap && ej<=i.end 
=> since ej<=i.end, add another room -> i, next i
ele next j 
*/
class Solution {
public:
    int minMeetingRooms(vector<Interval>& intervals) {
    	vector<int> starts, ends;
    	for (auto i:intervals){ // store with idx
    		starts.push_back(i.start); 
    		ends.push_back(i.end);
    	}
    	sort(starts.begin(),starts.end());
    	sort(ends.begin(),ends.end());
    	int ans = 0, j = 0;
    	for (int i = 0; i < intervals.size(); ++i)
    		if (starts[i] < ends[j])
    			++ ans; // rnum[i.idx] = ans++;
    		else // can schedule after j
    			++ j; // rnum[i.idx] = rnum[j++.idx]
    	return ans;
    }
};

follow up问题：把每个 meeting room 中的 intervals 打印出来

Given two lists of intervals, find their overlapping intervals. For example: l1: [1,5], [7,10], [12,18], [22,24], l2: [3,8], [13,15], [16,17], [18,21], [22,23]
returns [3,5], [7,8], [13,15], [16,17], [18,18], [22,23]

// if there is something wrong, please correct me
two pointers: i, j
if Ai overlap Bj, 
  cout << overlap
  if ie = je, i++, j++,
  else
    if is <= js, i++, je = ie + 1
    else j++, ie = je +1
else 
  if is < ie <= js < je, i++
  else j++

//sort with start & sort with end, then
int count = 0, start = 0;
		for (int i = 0, j = 0; j < ends.length;) {
			if (i < begs.length && begs[i] < ends[j]) {
				if (++count == 2) {
					// enter overlap
					start = begs[i];
				}
				i++;
			} else if (i == begs.length || begs[i] > ends[j]) {
				if (--count == 1) {
					// exit overlap
					res.add(new Interval(start, ends[j]));
				}
				j++;
			} else {
				// begs[i] == ends[j]
				if (count > 1) {
					// already in overlap
					continue;
				}
				res.add(new Interval(begs[i++], ends[j++]));
			}
		}
		return res;

N个员工，每个员工有若干个interval表示在这段时间是忙碌的。求所有员工都不忙的intervals。每个subarray都已经sort好。
举例： [
[[1, 3], [6, 7]],
[[2, 4]],
[[2, 3], [9, 12]].
]
返回 [[4, 6], [7, 9]]

//sort with start & sort with end, then
int count = 0, start = 0;
		for (int i = 0, j = 0; i < begs.length;) {
			if (begs[i] < ends[j]) {
				if (++count == 1) {
					// exit free time
					if (start > 0) {
						res.add(new Interval(start, begs[i]));
					}
				}
				i++;
			} else if (begs[i] > ends[j]) {
				if (--count == 0) {
					// start free zone
					start = ends[j];
				}
				j++;
			} else {
				// begs[i] == ends[j]
				i++;
				j++;
			}
			System.out.println(res);
		}
		return res;