Interval Insert

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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].
Solution: For example 2:
           1. compare [1,2] with [4,9], then insert [1,2];
           2. merge [3,5] with [4,9], get newInterval = [3,9];
           3. merge [6,7] with [3,9], get newInterval = [3,9];
           4. merge [8,10] with [3,9], get newInterval = [3,10];
           5. compare [12,16] with [3,10], insert newInterval [3,10], then all the remaining intervals...


代码：

 /**  
  * 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 Solution {  
 public:  
   vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {  
     vector<Interval> res;  
     if (intervals.empty()) {  
       res.push_back(newInterval);  
       return res;  
     }  
     bool inserted = false;  
     for (int i = 0; i < intervals.size(); ++i) {  
       if (inserted || intervals[i].end < newInterval.start) { // non-overlaping  
         res.push_back(intervals[i]);  
       } else if (newInterval.end < intervals[i].start) {  
         res.push_back(newInterval);  
         res.push_back(intervals[i]);  
         inserted = true;  
       } else { // update new interval  
         newInterval.start = min(intervals[i].start, newInterval.start);  
         newInterval.end = max(intervals[i].end, newInterval.end);  
       }  
     }  
     if (!inserted) res.push_back(newInterval);        
     return res;  
   }  
 };  

Merge Intervals

来源：Leetcode

原帖：http://oj.leetcode.com/problems/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].
Solution: Sort in ascending order of 'start'. Traverse the 'intervals', merge or push...

代码：

 /**  
  * Definition for an interval.  
  * struct Interval {  
  *   int start;  
  *   int end;  
  *   Interval() : start(0), end(0) {}  
  *   Interval(int s, int e) : start(s), end(e) {}  
  * };  
  */  
 bool compare(const Interval& a, const Interval& b) {  
   return a.start < b.start;  
 }  
   
 class Solution {  
 public:  
   vector<Interval> merge(vector<Interval> &intervals) {  
     int N = intervals.size();  
     if (N <= 1) return intervals;  
     sort(intervals.begin(), intervals.end(), compare);  
     vector<Interval> res;  
     Interval last = intervals[0];  
     for (int i = 1; i < N; ++i) {  
       if (intervals[i].start > last.end) {  
         res.push_back(last);  
         last = intervals[i];  
       } else {  
         last.end = max(last.end, intervals[i].end);  
       }  
     }   
     res.push_back(last); // push back the last one  
     return res;  
   }  
 };  

Meeting Room

来源：Facebook Phone Interview (2/12/2015)

原帖：http://www.fgdsb.com/2015/01/30/meeting-rooms/

题目 1：
write a function that detects conflicts in meeting schedules.

input: a list of schedules [(s1, e1), (s2, e2), ]

output: return True if there's any conflict, and False otherwise

代码：

 struct Interval {  
   double start;  
   double end;  
   Interval(double a, double b) : start(a), end(b) {}  
 };  
   
 bool compare(const Interval& a, const Interval& b) {  
   return a.start < b.start;  
 }  
   
 const double eps = 1.0e-12;  
 int compareDoulbe(double a, double b) {  
   if (b == 0) b += eps;  
   if (a == 0) a += eps;  
   double err = (a-b)/b; // a/b - 1;  
   return err > eps ? 1 : err < -eps ? -1 : 0;   
 }  
   
 bool existConflict(vector<Interval>& meetings) {  
   if (meetings.empty()) return false;  
   sort(meetings.begin(), meetings.end(), compare);  
   int N = meetings.size();  
   for (int i = 1; i < N; ++i) {  
     if (compareDouble(meetings[i].start, meetings[i-1].end)) {  
       return true;  
     }  
   }  
   return false;  
 }  

// test case
// {}, {{1.0,2.0}, {2.5, 3.5}, {5.2, 6.0}, }
// {{1.0, 5.0}, {3.6, 9.0}}

题目 2：

write a function that finds the minimum number of rooms that can accommodate given schedules.

代码：http://www.fgdsb.com/2015/01/30/meeting-rooms/

 bool compare(const pair<int,int>& a, const pair<int, int>& b) {  
   if (a.first == b.first) {  
     return a.second > b.second;  
   }  
   return a.first < b.first;  
 }  
   
 int minimumRoom(vector<Interval>& meetings) {  
   if (meetings.empty()) return 0;  
   vector<pair<int,int> > arrays;  
   for (int i = 0; i < meetings.size(); ++i) {  
     arrays.push_back(meetings[i].start, 0);  //可以使用start, -end来代替pair
     arrays.push_back(meetings[i].end, 1);  
   }  
   sort(arrays.begin(), arrays.end(), compare); //  
   int min = 0, res = 0;  
   for (int i = 0; i < arrays.size(); ++i) {  
     if (arrays[i].second == 0) {  
       min++;  
     } else {  
       min--;  
     }  
     res = max(min, res);  
   }  
   return res;   
 }  

另外一份代码：

 int min_rooms(vector<Interval>& meetings) {  
   vector<int> times;  
   for(auto m : meetings) {  
     times.push_back(m.begin);  
     times.push_back(-m.end);  
   }    
   sort(times.begin(), times.end(), [](int a, int b){  
     return abs(a) == abs(b) ? a < b : abs(a) < abs(b);  
   });    
   int ret = 0, cur = 0;  
   for(auto t : times) {  
     if(t >= 0) ret = max(ret, ++cur);  
     else --cur;  
   }  
   return ret;  
 }  

// test case

// {}, {{1.0, 3.0}, {3.5, 5.0}, {6.8, 10.0}} return 1 

// {{1.0, 8.0}, {2.0,6.0},{3.0, 7.0}} return 3 // 

// {{1.0, 4.0}, {2.0, 7.0}, {5.0, 8.0}} return 2;

Intersect & Union of Two Sorted Arrays

来源：itint5

原帖：http://www.itint5.com/oj/#43

题目：
有2个大小为n和m的有序数组（升序）a和b，实现2个函数arrayUnion和arrayIntersect计算
它们的并集和交集，结果也必须有序。
提示：时间复杂度O(n+m)，空间复杂度O(1)。
如果m >> n， 对于m数组做binary search可能会更有效。

代码：
1] Union

 vector<int> arrayUnion(vector<int> &a, vector<int> &b) {  
   int N = a.size(), M = b.size();  
   int i = 0, j = 0;  
   vector<int> res(N+M);  
   int k = 0;  
   while (i < N || j < M) {  
     int value;  
     if (i == N) {  
       value = b[j++];  
     } else if (j == M) {  
       value = a[i++];  
     } else {  
       value = a[i] < b[j] ? a[i++] : b[j++];  
     }  
       
     if (k == 0 || res[k - 1] != value)  
       res[k++] = value;  
   }  
   res.resize(k);  
   return res;  
 }  

2] Intersection

 vector<int> arrayIntersect(vector<int> &a, vector<int> &b) {  
   int N = a.size(), M = b.size();  
   vector<int> res(min(N, M));  
   int i = 0, j = 0, k = 0;  
   while (i < N && j < M) {  
     if (a[i] == b[j]) {  
       if (k == 0 || res[k-1] != a[i]) { //   
         res[k++] = a[i];  
         i++; j++;  
       }   
     } else if (a[i] < b[j]) {  
       i++;  
     } else {  
       j++;  
     }    
   }  
   res.resize(k);  
   return res;  
 }  
   

Sort Colors

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sort-colors/

题目：
Given an array with n objects colored red, white or blue, sort them so that objects of the same color
are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note:
You are not suppose to use the library's sort function for this problem.
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort.
First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with
total number of 0's, then 1's and followed by 2's.
Could you come up with an one-pass algorithm using only constant space?

Solution: 0 0 0 1 1 1 1 ...... 2 2 2 2
               |         |      |
             zero        i     two
              ->        ->     <-

代码：

 class Solution {  
 public:  
   //Version 1: 从左到右遍历  
   void sortColors(int A[], int n) {  
     int zero = 0, two = n-1;  
     int i = 0;  
     while (i <= two) {  
       switch(A[i]) {  
       case 0:  
         swap(A[i++], A[zero++]);  
         break;  
       case 1:  
         i++;  
         break;  
       case 2:  
         swap(A[i], A[two--]);  
       }  
     }  
   }  
 };  
   
 class Solution {  
 public:  
   //Version 2: partition两次;  
   int partition(int A[], int len, int val) {  
     int i = 0, j = len -1;  
     while (i <= j) {  
       while (i <= j && A[i] <= val) i++;  
       while (i <= j && A[j] > val) j--;  
       if (i < j) swap(A[i++], A[j--]);  
     }  
     return i;  
   }  
     
   void sortColors(int A[], int n) {  
     int start = partition(A, n, 0);  
     partition(A + start, n - start, 1);  
   }  
 };  

Sort List (Insert Sort)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/insertion-sort-list/

题目：
Sort a linked list using insertion sort.

代码：

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
 class Solution {  
 public:  
     ListNode *insertionSortList(ListNode *head) {  
         if(!head) return NULL;  
         ListNode dummy(0); // 1->2->5->null insert 3;     
         while (head) { // head: insert linked list node  
             ListNode* node = &dummy;  
             while (node->next != NULL && node->next->val <= head->val) {  
                 node = node->next;  
             }       
             ListNode* temp = head->next;  
             head->next = node->next;  
             node->next = head;  
             head = temp;  
         }  
         return dummy.next;  
     }  
 };  

Sort List (Merge Sort)

来源：Leetcode

原帖：http://oj.leetcode.com/problems/sort-list/

题目：
Sort a linked list in O(nlogn) time using constant space complexity.

代码：1] 考虑merge sort

 /**  
  * Definition for singly-linked list.  
  * struct ListNode {  
  *   int val;  
  *   ListNode *next;  
  *   ListNode(int x) : val(x), next(NULL) {}  
  * };  
  */  
    
 class Solution {  
 public:  
     int getLength(ListNode *head) {  
         int length = 0;  
         while (head) {  
             length++;  
             head = head->next;  
         }  
         return length;  
     }  
   
     ListNode* mergeList(ListNode *head1, ListNode *head2) {  
         ListNode dummy(0);   
         ListNode *cur = &dummy;  
         while (head1 && head2) {  
             ListNode **min = head1->val < head2->val ? &head1 : &head2;  
             cur->next = *min;  
             cur = cur->next;  
             *min = (*min)->next;  
         }  
         if (!head1) cur->next = head2;  
         if (!head2) cur->next = head1;  
         return dummy.next;  
     }  
   
     ListNode* sortLinkedList(ListNode* &head, int N) {  
         if (N == 0) return NULL;  
         if (N == 1) {  
             ListNode* cur = head;  
             head = head->next; // update head pointer  
             cur->next = NULL; // end of list  
             return cur;  
         }  
         int half = N / 2;  
         ListNode* head1 = sortLinkedList(head, half);  
         ListNode* head2 = sortLinkedList(head, N - half);  
         return mergeList(head1, head2);  
     }  
   
     ListNode *sortList(ListNode *head) {  
         return sortLinkedList(head, getLength(head));  
     }  
 };  

Inverse Pairs

来源：Meetqun, 一亩三分地，Google

原帖：http://www.fgdsb.com/2015/01/03/inverse-pairs/

题目：
Given an integer array, return the number of all inverse pairs. For example:
{7, 5, 6, 4}
There are five inverse pairs in total:
(7,6), (7,5), (7,4), (6,4), (5,4)
The result should be 5.

思路：
用BST, 线段树，或者merge sort. 从后向前merge然后计算pair number.

代码：

 int mergeSort(vector<int>& num, int s, int e, vector<int>& dup) {   
     if (s >= e) return 0;   
     int mid = s + (e - s) / 2;   
     int l = mergeSort(num, s, mid, dup);   
     int r = mergeSort(num, mid+1, e, dup);   
     //cout << "start: " << s << " end " << e << " mid " << mid;   
     //cout << " l " << l << " r " << r << endl;   
   
     int sum = l + r;   
     for (int i = s; i <= e; ++i) {   
         dup[i] = num[i];   
     }   
     int cur = e, i = mid, j = e; // back -> front   
     while (i >= s && j > mid) {   
         if (dup[i] <= dup[j]) {   
             num[cur--] = dup[j--];   
         } else if (dup[i] > dup[j]) {   
             num[cur--] = dup[i--];   
             sum += j - mid;   
         }   
     }   
     while (i >= s) {   
         num[cur--] = dup[i--];   
     }   
     while (j > mid) {   
         num[cur--] = dup[j--];   
     }   
     return sum;   
 }   
   
 int inverse(vector<int>& num) {   
     if (num.empty() || num.size() == 1) return 0;   
     vector<int> dup(num);   
     return mergeSort(num, 0, num.size()-1, dup);   
 }   
   
 int main() {   
     vector<int> num = {7, 5, 6, 4};   
     cout << inverse(num) << endl;   
     return 0;   
 }   

K-th Largest Sum from Two Sorted Array

来源：Meetqun, Google

原帖：http://www.meetqun.com/thread-2183-1-1.html

题目：
X+Y 第K大. X =[1,2,3] Y = [2,3,4], S = {x+y| x属于X, y属于Y}, 求S中的第K大数。下面这个链接给了解释。http://blog.csdn.net/shoulinjun/article/details/19179243

思路：X,Y是从大到小排列数组。将X拆分成X[i] + Y[0,...,n-1]的形式。
X[0] + Y[0], X[0] + Y[1], ...X[0] + Y[n-1]
X[1] + Y[0], X[1] + Y[1], ...X[1] + Y[n-1]
X[m-1] + Y[0], X[m-1] + Y[1],...., X[m-1] + Y[n-1]
然后用最大堆来解决问题。

代码:

 struct Pair {   
     int ai,bj;   
     int val;   
     Pair(int i, int j, int v) : ai(i), bj(j), val(v) {}    
 };   
   
 class compare {   
 public:   
     bool operator() (const Pair& a, const Pair& b) {   
         return a.val < b.val;   
     }   
 };   
   
 vector<int> res; // global variable   
 int findKthElement(vector<int>& A, vector& B, int k) {   
     priority_queue<Pair, vector<Pair>, compare> q;   
     for (int i = 0; i < A.size(); ++i) {   
         q.push(Pair(i,0,A[i] + B[0]));   
     }   
     int count = 0;   
     while (!q.empty() && count < k) {   
         int element = q.top().val;    
         int i = q.top().ai, j = q.top().bj;   
         //cout << element << endl;   
         res.push_back(element);   
         q.pop();   
         if (++count == k) return element;   
         if (j < B.size()-1) {   
             q.push(Pair(i,j+1,A[i]+B[j+1]));   
         }   
     }   
     return -1; // not found;   
 }   
   
 int main() {   
     vector<int> A = {6,3,2};   
     vector<int> B = {5,4,1};   
     int k = 9;   
     findKthElement(A,B,k);   
     //for (auto i : res) cout << i << " ";   
     return 0;   
 }