//
// Created by 罗炳国 on 2023/10/13.
//

#ifndef PFJ_CODE025_AVOIDFLOOD_H
#define PFJ_CODE025_AVOIDFLOOD_H
#include "commonHeader.h"

// leetcode 1488:https://leetcode.cn/problems/avoid-flood-in-the-city/

class code025_avoidFlood {
public:
    typedef struct {
        int day;// 化解第几天下雨，用于优先级排序
        int num;// 抽第几号湖泊
    } task;

    struct cmp {
        bool operator()(task &a, task &b) {
            return a.day > b.day;
        }
    };

    vector<int> avoidFlood(vector<int>& rains) {
        int N = rains.size();
        std::priority_queue<task, vector<task>, cmp> tasks;
        std::unordered_map<int, list<int>> rmap;//未来湖泊-下雨天
        std::unordered_set<int> lakes;
        std::vector<int> ans(N, -1);

        // 建立湖泊下雨天关系表
        for (int i = 0; i < N; i++) {
            auto iter = rmap.find(rains[i]);

            if (iter == rmap.end()) {
                list<int> v;
                v.push_back(i);
                rmap[rains[i]] = v;
            } else {
                iter->second.push_back(i);
            }
        }

        for (int i = 0; i < N; i++) {
            if (rains[i] == 0) {// 晴天，干活儿了
                if (tasks.empty()) //无活儿可干
                    ans[i] = 1; // 去干抽一号坑
                else {
                    task t = tasks.top();
                    tasks.pop();
                    ans[i] = t.num;
                    std::cout << i <<  " 抽水：" << t.num << endl;
                    lakes.erase(t.num);
                }
            } else {
                if (lakes.find(rains[i]) != lakes.end()) {
                    std::cout << i << endl;
                    return {};
                }
                auto &li = rmap[rains[i]];
                li.pop_front();
                lakes.insert(rains[i]);
                if (!li.empty()) {
                    task t;
                    t.day = li.front();
                    t.num = rains[i];
                    tasks.push(t);
                }

            }
        }
        return ans;
    }

    void test() {
        vector<int> vec {1,2,0,2,3,0,1};
        vector<int> ans = avoidFlood(vec);
        vecShow(ans);
    }
};


#endif//PFJ_CODE025_AVOIDFLOOD_H