<8-4> 그리디 - 배치 시스템 (BatchSystem)

### Greedy ###

### SRM 481 Div2 Level 3 ###

<소스코드>

#include <algorithm>
#include <string>
#include <vector>
#include <map>
using namespace std;
 
typedef long long int lli;
 
struct P { 
    int i, duration; 
    P(int i, int duration) : i(i), duration(duration) {}
};
 
struct userInfo {
    vector<P> v;
    lli sum;
    userInfo(vector<P> v, lli sum) : v(v), sum(sum) {}
};
 
bool cmp(P a, P b)
{
    return a.i < b.i;
}
 
bool cmp2(userInfo a, userInfo b)
{
    return a.sum != b.sum ? a.sum < b.sum : a.v[0].i < b.v[0].i;
}
    
class BatchSystem {
public:
    vector<int> schedule(vector <int> duration, vector <string> user) {
        int userIdx=0;
        map<string, int> msi;
        vector<userInfo> info;
        for(int i=0; i<duration.size(); i++) {
            if(msi.find(user[i]) == msi.end()) {
                msi[user[i]] = ++userIdx;
                vector<P> v; v.push_back(P(i, duration[i]));
                info.push_back(userInfo(v, duration[i]));
            }
            else {
                int idx = msi[user[i]]-1;
                info[idx].sum += duration[i];
                info[idx].v.push_back(P(i, duration[i]));
            }
        }
            
        for(int i=0; i<info.size(); i++) {
            sort(info[i].v.begin(), info[i].v.end(), cmp);
        }
 
        sort(info.begin(), info.end(), cmp2);
        
        vector<int> ans;
        for(int i=0; i<info.size(); i++) {
            for(int j=0; j<info[i].v.size(); j++) {
                ans.push_back(info[i].v[j].i);
            }
        }
        return ans;
    }
};