// Sort: merge sort & quick sort is more important
// Template:
// Quick Sort:
// 1. get separate point. q[l] q[(l+r)/2] q[r]. The value.
// 2. adjust the range. select x and make left part <= x, right part >= x.
// 3. recursive processing left & right part.
// Template: 
void QuickSort(const int l, const int r, std::vector<int>& arr) {
  if (l >= r) return;
  int num = arr[l + (r - l)/2];
  int i = l - 1;
  int j = r + 1;
  while (i < j) {
    do {
      ++i;
    } while (arr[i] < num);
    do {
      --j;
    } while (arr[j] > num);
    if (i < j)
      std::swap(arr[i], arr[j]);
  }
  QuickSort(arr, l, j);
  QuickSort(arr, j+1, r);
}

int CalculateKthLargestNumber(const int l, const int r, 
                              const int k, std::vector<int>& nums) {
  if (l >= r) return nums[l];
  int i = l - 1;
  int j = r + 1;
  const int mid = nums[l + (r - l)/2];
  while (i < j) {
    do {
      ++i;
    } while (nums[i] < mid);
    
    do {
      --j;
    } while (nums[j] > mid);
    
    if (i < j) {
      std::swap(nums[i], nums[j]);
    }
  }
  return j + 1 >= k ? CalculateKthLargestNumber(l, j, k, nums) : 
                      CalculateKthLargestNumber(j+1, r, k, nums);
}

// Merge sort.
// 1. get the separate point. The index.
// 2. recursive call left & right
// 3. merge the sorting with both left & right parts.
void MergeSort(const int l, const int r, std::vector<int>& nums) {
  if (l >= r) return;
  const int mid = l + (r - l)/2;
  MergeSort(l, mid, nums);
  MergeSort(mid+1, r, nums);
  std::vector<int> tmp(r - l + 1);
  int i = l; 
  int j = mid+1;
  int cnt = 0;
  while (i <= mid && j <= r) {
    if (nums[i] <= nums[j]) {
      tmp[cnt++] = nums[i++];
    } else {
      tmp[cnt++] = nums[j++];
    }
  }
  
  while (i <= mid) tmp[cnt++] = nums[i++];
  while (j <= r) tmp[cnt++] = nums[j++];
  for (int i = l, j = 0; i <= r; ++i, ++j) {
    nums[i] = tmp[j];
  }    
}

// 853. Car Fleet
int carFleet(int target, vector<int>& position, vector<int>& speed) {
  if (position.empty()) return 0;
  vector<pair<int, double>> cars;
  for (int i = 0; i < size(position); ++i) {
    cars.emplace_back(position[i], 1.0*(target - position[i])/speed[i]);
  }
  sort(begin(cars), end(cars), [](const pair<int, double>& c1, 
                                  const pair<int, double>& c2) {
    return c1.first > c2.first;
  });
  int count = 0;
  for (int i = 1; i < size(cars); ++i) {
    if (cars[i].second <= cars[i-1].second)
      cars[i] = cars[i-1];
    else 
      ++count;
  }
  return count + 1;
}