//
// Created by 罗炳国 on 2023/9/24.
//

#ifndef PFJ_CODE21_COVERMAX_H
#define PFJ_CODE21_COVERMAX_H

#include "commonHeader.h"

/**
 * 给定很多线段，每个线段都有两个数[start, end]，
 * 表示线段开始位置和结束位置，左右都是闭区间
 * 规定：
 * 1）线段的开始和结束位置一定都是整数值
 * 2）线段重合区域的长度必须>=1 如[1, 3], [3, 7]重合长度为0
 * 返回线段最多重合区域中，包含了几条线段
 * [1, 5], [2, 6], [2, 5], [4, 7], [2, 9] 最大重合度为5，重合区间为[4, 5]
 * */

struct
{
    bool operator()(vector<int>& a, vector<int>& b) const {return a.at(0) < b.at(0);}
} comp;



class coverMax {
public:
    int maxCover(vector<vector<int>> &lines) {
        int ret = 0, N = lines.size();
        std::sort(lines.begin(), lines.end(), comp);
        std::priority_queue<int, vector<int>, std::greater<int>> pq;
        for (int i = 0; i < N; i++) {
            if (pq.empty() || lines[i][0] < pq.top()) {
                pq.push(lines[i][1]);
            } else {
                ret = std::max(ret, (int)pq.size());
                while (!pq.empty() && lines[i][0] > pq.top() ) {
                    pq.pop();
                }
                pq.push(lines[i][1]);
            }
        }
        ret = std::max(ret, (int)pq.size());
        return ret;
    }

    void test() {
        /**
         * [1, 5],[3, 7], [9, 12], [4, 7], [3, 10] 最大重合度为4，[4, 5]
         * */
         vector<vector<int>> arr {{1, 5}, {3, 7}, {9, 12}, {4, 7}, {3, 10}};
         int ans = maxCover(arr);
         std::cout << "ans:" << ans << endl;
         // [1, 5], [2, 6], [2, 5], [4, 7], [2, 9]
         vector<vector<int>> arr2 {{1, 5}, {2, 6}, {2, 5}, {4, 7}, {2, 9}};
         ans = maxCover(arr2);
         std::cout << "ans:" << ans << endl;
    }
private:
    bool compare(const vector<int>& a, const vector<int>& b)
    {
        return a.at(0) > b.at(0);
    }
};

#endif//PFJ_CODE21_COVERMAX_H