Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- struct Node {
- int time;
- bool isBegin;
- };
- void swap(Node *a, Node *b){
- Node temp = *a;
- *a = *b;
- *b = temp;
- }
- bool compare(Node *a, Node *b){
- if (a->time < b->time) {
- return true;
- }
- else if (a->time == b->time) {
- if (a->isBegin == false) {
- return true;
- }
- else {
- return false;
- }
- }
- else {
- return false;
- }
- }
- void siftDown(Node *beg, int size, int i){
- int left = 2 * i + 1;
- int right = 2 * i + 2;
- int max = i;
- if (left < size && compare(beg + i, beg + left)){
- max = left;
- }
- if (right < size && compare(beg + max, beg + right)){
- max = right;
- }
- if (max != i){
- swap(beg + i, beg + max);
- siftDown(beg, size, max);
- }
- }
- void buildHeap(Node *beg, int size){
- for (int i = size / 2 - 1; i >= 0; --i){
- siftDown(beg, size, i);
- }
- }
- void heapSort(Node *beg, Node *end){
- int size = end - beg + 1;
- buildHeap(beg, size);
- for (int i = size - 1; i >= 0; --i){
- swap(beg, beg + i);
- siftDown(beg, i, 0);
- }
- }
- int main(){
- int n;
- cin >> n;
- Node* arr = new Node[2 * n];
- for (int i = 0; i < n; i++) {
- cin >> arr[2 * i].time >> arr[2 * i + 1].time;
- arr[2 * i + 1].time += arr[2 * i].time;
- arr[2 * i].isBegin = true;
- arr[2 * i + 1].isBegin = false;
- }
- heapSort(arr, arr + 2 * n - 1);
- int answer = 0;
- int currAnswer = 0;
- for (int i = 0; i < 2 * n; ++i) {
- if (arr[i].isBegin == true) {
- currAnswer++;
- }
- else {
- currAnswer--;
- }
- if (currAnswer > answer) {
- answer = currAnswer;
- }
- }
- cout << answer;
- delete[] arr;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement