EPI-Sorting

//sort() 数组排序
//list::sort() 链表排序

vector<int> IntersectTwoSortedArrays(const vector<int>& A,
                                     const vector<int>& B) {
  // TODO - you fill in here.
  vector<int> ret;
  int a_st = 0, b_st = 0;
  while (a_st < A.size() && b_st < B.size()) {
      if (A[a_st] == B[b_st] && (ret.empty() || ret.back() != A[a_st])) {
          ret.emplace_back(A[a_st]);
          ++a_st, ++b_st;
      } else if (A[a_st] < B[b_st]) {
          ++a_st;
      } else {
          ++b_st;
      }
  }
  return ret;
}

void MergeTwoSortedArrays(vector<int>& A, int m, const vector<int>& B, int n) {
  // TODO - you fill in here.
  int st = m - 1, ed = A.size() - 1;
  while (st >= 0) {
      A[ed--] = A[st--];
  }
  //ed 指向空位置
  int A_st = ed + 1, B_st = 0, A_curr = 0;
  while (A_st < A.size() && B_st < B.size()) {
      if (A[A_st] <= B[B_st]) {
          A[A_curr++] = A[A_st++];
      } else {
          A[A_curr++] = B[B_st++];
      }
  }
  while (A_st < A.size()) {
      A[A_curr++] = A[A_st++];
  }
  while (B_st < B.size()) {
      A[A_curr++] = B[B_st++];
  }
  return;
}

void MergeTwoSortedArrays(vector<int>& A, int m, const vector<int>& B, int n) {
  // TODO - you fill in here.
  int A_curr = m + n - 1, A_st = m - 1, B_st = n - 1;
  while (A_st >= 0 && B_st >= 0) {
      if (A[A_st] >= B[B_st]) {
          A[A_curr--] = A[A_st--];
      } else {
          A[A_curr--] = B[B_st--];
      }
  }
  while (B_st >= 0) {
      A[A_curr--] = B[B_st--];
  }
  return;
}

void EliminateDuplicate(vector<Name>* names) {
  // TODO - you fill in here.
  vector<Name>& name_ref = *names;
  std::sort(name_ref.begin(), name_ref.end());
  int l_idx = 0, r_idx = 1;
  while (r_idx < name_ref.size()) {
      if (name_ref[r_idx].first_name == name_ref[l_idx].first_name) {
          ++r_idx;
      } else {
          name_ref[++l_idx] = name_ref[r_idx++];
      }
  }
  if (l_idx == name_ref.size() - 1) {
      return;
  }
  int residual = name_ref.size() - l_idx - 1;
  while (residual-- > 0) {
      name_ref.pop_back();
  }
  return;
}

struct Event {
  int start, finish;
};

struct EndPoint {
    bool operator<(const EndPoint& e) const{
        // 将时间靠前的拍在前面 如果时间相同 将start 排在 end 前面
        return this->time != e.time ? this->time < e.time : (this->isStart && !e.isStart);
    }
    int time;
    bool isStart;
};
int FindMaxSimultaneousEvents(const vector<Event>& A) {
  // TODO - you fill in here.
  vector<EndPoint> E;
  for (auto &each : A) {
      E.push_back({each.start, true});
      E.push_back({each.finish, false});
  }
  //按照时间排序
  std::sort(E.begin(), E.end());

  int max_event_cnt = 0, event_cnt = 0;
  for (auto &each : E) {
      if (each.isStart) {
          ++event_cnt;
          max_event_cnt = std::max(event_cnt, max_event_cnt);
      } else {
          --event_cnt;
      }
  }
  return max_event_cnt;
}

struct Interval {
  int left, right;
};
struct EndPoint {
    bool operator<(const EndPoint& e) const {
        return point != e.point ? point < e.point : (isLeft && !e.isLeft);
    }
    int point;
    bool isLeft;
};
vector<Interval> AddInterval(const vector<Interval>& disjoint_intervals,
                             Interval new_interval) {
  // TODO - you fill in here.
  vector<EndPoint> E;
  for (auto &each: disjoint_intervals) {
      E.push_back({each.left, true});
      E.push_back({each.right, false});
  }
  E.push_back({new_interval.left, true});
  E.push_back({new_interval.right, false});

  std::sort(E.begin(), E.end());

  vector<Interval> ret;
  bool is_new_interval = true;
  int st = 0, left_cnt = 0;
  for (auto &each : E) {
      if (each.isLeft) {
          ++left_cnt;
          if (is_new_interval) {
              st = each.point;
              is_new_interval = false;
          }
      } else {
          --left_cnt;
      }
      if (left_cnt == 0) {
          ret.push_back({st, each.point});
          is_new_interval = true;
      }
  }
  return ret;
}

struct Interval {
  struct Endpoint {
    bool is_closed;
    int val;
  };

  Endpoint left, right;
};

struct Point {
    bool operator<(const Point& p) const {
//        return val != p.val ? val < p.val : (is_left && !p.is_left);
        if (val != p.val) {
            return val < p.val;
        }
        // 元素相等 两个都是开区间
        if (!is_closed && !p.is_closed) {
            // 一前一后 将right 放在left前
            return !is_left && p.is_left;
        }

        // 元素相等 一开一闭 都是right 开区间放前
        if (!is_left && !p.is_left) {
            return !is_closed && p.is_closed;
        }
        // 元素相等 一开一闭 都是left 闭区间放前
        if (is_left && p.is_left) {
            return is_closed && !p.is_closed;
        }
        // 元素相等 一开一闭 left放在right前
        return is_left && !p.is_left;
    }
    int val;
    bool is_left;
    bool is_closed;
};
vector<Interval> UnionOfIntervals(vector<Interval> intervals) {
  // TODO - you fill in here.
  vector<Point> P;
  for (auto &each : intervals) {
      P.push_back({each.left.val, true, each.left.is_closed});
      P.push_back({each.right.val, false, each.right.is_closed});
  }
  std::sort(P.begin(), P.end());
  vector<Interval> ret;

  bool is_new_intervals = true, left_closed = false;
  int left_idx = 0, left_cnt = 0;
  for (auto &each : P) {
    if (each.is_left) {
        ++left_cnt;
        if (is_new_intervals) {
            left_idx = each.val;
            left_closed = each.is_closed;
            is_new_intervals = false;
        }
    } else {
        --left_cnt;
    }
    if (left_cnt == 0) {
        ret.push_back({{left_closed, left_idx},{each.is_closed, each.val}});
        is_new_intervals = true;
    }
  }
  return ret;
}

void GroupByAge(vector<Person>* people) {
  // TODO - you fill in here
  vector<Person>& p_ref = *people;
  std::unordered_map<int, vector<string>> age_to_name;
  for (auto &each: p_ref) {
      age_to_name[each.age].emplace_back(each.name);
  }
  int c_idx = 0;
  for (auto &each : age_to_name) {
      for (auto &name: each.second) {
          p_ref[c_idx++] = {each.first, name};
      }

  }
  return;
}

void GroupByAge(vector<Person>* people) {
  // TODO - you fill in here
  vector<Person>& p_ref = *people;
  std::unordered_map<int, int> age_to_cnt;
  for (auto &each: p_ref) {
      ++age_to_cnt[each.age];
  }
  std::unordered_map<int, int> age_to_offset;
  int offset = 0;
  for (auto &each : age_to_cnt) {
      age_to_offset[each.first] = offset;
      offset += each.second;
  }

  int c_idx = 0;
  while (!age_to_offset.empty()) {
      // 将from 的元素替换到to
      auto from = age_to_offset.begin();
      // 找到from处年龄对应的offset位置的元素的年龄
      auto to = age_to_offset.find(p_ref[from->second].age);
      // 上一步找到两个年龄的offset, 将from替换到to， 此时to位置的元素处于正确的位置， 而from未必
      std::swap(p_ref[from->second], p_ref[to->second]);

      --age_to_cnt[to->first];
      if (age_to_cnt[to->first] > 0) {
          ++age_to_offset[to->first];
      } else {
          age_to_offset.erase(to->first);
      }
  }
  return;
}

  // Checks if team0 can be placed in front of team1.
  static bool ValidPlacementExists(const Team& team0, const Team& team1) {
    // TODO - you fill in here.
    auto team0_sort(team0.players_);
    auto team1_sort(team1.players_);
    std::sort(team0_sort.begin(), team0_sort.end());
    std::sort(team1_sort.begin(), team1_sort.end());
    for (int i = 0; i < team0_sort.size(); ++i) {
        if (!(team0_sort[i] < team1_sort[i])) {
            return false;
        }
    }
    return true;
  }

shared_ptr<ListNode<int>> MergeTwoSortList(shared_ptr<ListNode<int>> L0, shared_ptr<ListNode<int>> L1) {
    auto dummy_head = make_shared<ListNode<int>>(ListNode<int>{0, nullptr});

    auto ptr = dummy_head;
    while (L0 && L1) {
        if (L0->data < L1->data) {
            ptr->next = L0;
            L0 = L0->next;
        } else {
            ptr->next = L1;
            L1 = L1->next;
        }
        ptr = ptr->next;
    }
    if (L0 == nullptr) {
        ptr->next = L1;
    } else {
        ptr->next = L0;
    }
    return dummy_head->next;
}

shared_ptr<ListNode<int>> StableSortList(shared_ptr<ListNode<int>> L) {
  // TODO - you fill in here.
  if (L == nullptr || L->next == nullptr) {
      return L;
  }
  // 用快慢指针找到链表中点
  shared_ptr<ListNode<int>> pre_slow = nullptr, slow = L, fast = L;
  while (fast && fast->next) {
      pre_slow = slow;
      fast = fast->next->next;
      slow = slow->next;
  }
  // 断开链表
  pre_slow->next = nullptr;
  // 递归归并排序
  return MergeTwoSortList(StableSortList(L), StableSortList(slow));
}

double FindSalaryCap(int target_payroll, vector<int> current_salaries) {
  // TODO - you fill in here.
  std::sort(current_salaries.begin(), current_salaries.end());
  // 当前cap下的薪水和
  double unadjusted_salary_sum = 0.;
  for (int i = 0; i < current_salaries.size(); ++i) {
      // cap以上的薪水和
      const double adjusted_salary_sum = current_salaries[i] * (current_salaries.size() - i);
      if (unadjusted_salary_sum + adjusted_salary_sum >= target_payroll) {
          return (target_payroll - unadjusted_salary_sum) / (current_salaries.size() - i);
      }
      unadjusted_salary_sum += current_salaries[i];
  }
  return -1;
}