BatchSystem

문제

n개의 작업 (1~50) 에 대해
int duration[] 과 string user[] 가 주어진다

작업 i 의 소요시간은 duration[i], 요청한 유저는 user[i] 가 된다

컴퓨터는 한 번에 1개의 작업만 처리할 수 있고
모든 사용자의 평균 대기 시간은 최소화 되어야 한다

0부터 시작하는 n개의 작업번호를, '처리순서' 대로
배열해서 int[] 로 리턴 (동률일 경우 유저 사전순서)

예시 입력

1)
{400, 100, 100, 100},
{"Danny Messer", "Stella Bonasera", "Stella Bonasera", "Mac Taylor"}

2)
{200, 200, 200},
{"Gil", "Sarah", "Warrick"}

3)
{100, 200, 50},
{"Horatio Caine", "horatio caine", "YEAAAAAAH"}

예시 출력

3 1 2 0 
0 1 2
2 0 1

생각의 변화

금방 끝나는 일부터 하면
오래 걸리는 일부터 하면

금방 끝나는 일부터 하되, 작업시간이 같은 사람이 여럿이라면

먼저 시작한 일은 다른 애들에게도 더해지므로 가급적 작은 것부터 수행

전체 합이 작은 걸로 정렬, 같은 경우 사전 순으로 정렬

일단 시작했으면 빨리 끝내는 것이 평균 낮추는 데 유리

같은 사람이면 모으는 걸로, 기존에 있는지 매번 체크

job 번호를 기억하고 있어야 한다
전체 기간도

pseudo code

struct job
{
    int totalduration;
    string user;
    vector<int> jobnumber;
};

schedule(duration, user)
    vector<job> queue
    
    queue.push_back({duration[0], user[0], {0}})

    n = duration.size()
    
    for (i=1  i<n  i++)
        found = false
        
        for (auto &e : queue)
            if (e.user == user[i])
                e.totalduration += duration[i]
                e.jobnumber.push_back(i)
                found = true
                
                break
                
        if (found == false)
            queue.push_back({duration[i], user[i], {i}});
    
    sort(queue.begin(), queue.end(), [](const job& a, const job& b) {
        if (a.totalduration == b.totalduration)
            return a.user < b.user
            
        return a.totalduration < b.totalduration
    })
    
    vector<int> res
    
    for (auto &e : queue)
        for (auto n : e.jobnumber)
            res.push_back(n)
            
            
    return res