#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;

template<typename T, class Container=vector<T>>
void print(Container data){
  for(auto item: data){
    cout << item.first << ": " << item.second << endl;
  }
}

int findNumberOfContentChildren(vector<int>& children, vector<int>& cookies)
{
  sort(children.begin(), children.end());
  sort(cookies.begin(), cookies.end());
  int child =0, cookie =0;
  while(child < children.size() && cookie < cookies.size()){
    if(children[child] <= cookies[cookie]) ++child;
    ++cookie;
  }
  return child;
}


int candy(vector<int>& ratings){
  int size = ratings.size();
  if(size< 2){
    return size;
  }
  vector<int> num(size, 1);
  
  //scan from left to right
  for(int i=1; i< size; ++i){
    if(ratings[i] > ratings[i-1]){
      num[i] = num[i-1] + 1;
    }
  }
  
  //scan from right to left
  for(int i= size-1; i >=1; --i){
    if(ratings[i] < ratings[i-1]){
      num[i-1] = max(num[i-1], num[i]+1);
    }
  }
  
  int res =0;
  for(int i =0; i< num.size(); ++i)
    res += num[i];
  return res;
}


int eraseOverlapIntervals(vector<pair<int, int>> & intervals)
{
  if(intervals.empty()){
    return 0;
  }
  int n = intervals.size();
  sort(intervals.begin(), 
      intervals.end(),
      [](pair<int, int> a, pair<int, int> b){
        return a.second < b.second;
      }
  );
  int total =0;
  int prev = intervals[0].second;
  for(int i=1; i< n; ++i){
    //overlapped with prev
    if(intervals[i].first < prev){
      //need to remove this interval
      total++;
    }else {
      prev = intervals[i].second;
    }
  }
  
  return total;
}


bool canPlaceFlower(vector<int> flowered, int  n){
  int i= 0; 
  int count =0;
  while(i < flowered.size()){
    if(flowered[i] == 0 && (i==0 || flowered[i-1] ==0) && (i==flowered.size() -1 || flowered[i+1] ==0))
        flowered[i] = 1;
        count++;
  }
  return n <= count;
}


int findMinArrowShots(vector<pair<int, int>>& pts)
{
  if(pts.empty()) return 0;
  sort(pts.begin(), pts.end());
  int res = 1; 
  int prev_end = pts[0].second;
  for(int i=1; i< pts.size(); ++i){
    //overlapped, can be shot by prev arrow
    //need to update the prev_end to the smaller one
    if(pts[i].first < prev_end)
          prev_end = min(prev_end, pts[i].second);
    else{
      res++;
      prev_end = pts[i].second;
    }
  }
}


vector<int> partitionLabels(string S) {
      // get the last seen index for each letter 'a' - 'z'
        int last[26];
        for (int i = 0; i < S.size(); ++i)
            last[S[i] - 'a'] = i;
        
        int boundary = 0, cnt = 0;
        vector<int> ans;
        for (int i = 0; i < S.length(); ++i) {
            // update boundary and cnt along the way
            char curChar = S[i];
            boundary = max(boundary, last[curChar - 'a']);
            cnt++;
            // if we reach the boundary, we collect result and reset count to 0
            if (i == boundary) {
                ans.push_back(cnt);
                cnt = 0;
            }
        }
        return ans;
}


int maxProfit(vector<int>& prices){
  int max_profit = 0;
  for(int i=0; i< prices.size(); ++i){
    if(prices[i] > prices[i-1])
      max_profit += prices[i] - prices[i-1];
  }
  return max_profit;
}


vector<pair<int, int>> reconstructQueue(vector<pair<int, int>>& people){
    vector<pair<int, int>> res;
    
    sort(
      people.begin(),
      people.end(),
      [](pair<int, int> a, pair<int, int> b){
        return a.first > b.first ||  (a.first == b.first && a.second < b.second);
      }
    );
    
    for(auto p: people){
      res.insert(res.begin() + p.second, p);
    }
    
    return res;
}



bool checkPossibility(vector<int>& nums){
  int count = 0;
  for(int i=1; i< nums.size(); ++i){
     if(nums[i] < nums[i-1]){
       count++;
       //within boundary
       if( i+1 < nums.size() && i-2 >=0){
         if(nums[i+1] < nums[i-1] && nums[i-2] > nums[i])
            return false;
       }
     }
     if(count > 1) return false;
  }
  return true;
}




int main() 
{
  
    vector<pair<int, int>>  intervals {
      {1, 2},
      {2, 4},
      {1, 3}
    };
    cout << "eraseOverlapIntervals: " << eraseOverlapIntervals(intervals) << endl;
    
    vector<pair<int, int>> people {
      {7,0},
      {4,4},
      {7,1},
      {5,0},
      {6,1},
      {5,2}
    };
    print<pair<int,int>>(reconstructQueue(people));
    return 0;
}