题解 | 任务调度

#include <bits/stdc++.h>
using namespace std;

struct Idea {
    int id;         // idea的序号
    int pmId;       // PM的序号
    int createTime; // 提出时间
    int priority;   // 优先级
    int duration;   // 所需时间
    int finishTime; // 完成时间
    
    Idea(int _id, int _pmId, int _createTime, int _priority, int _duration) : 
        id(_id), pmId(_pmId), createTime(_createTime), 
        priority(_priority), duration(_duration), finishTime(-1) {}
};

class Solution {
public:
    vector<int> solve(int n, int m, int p, vector<vector<int>>& ideas) {
        vector<int> result(p);
        vector<Idea*> allIdeas;
        
        // 创建idea生产队列（按创建时间排序）
        auto createCmp = [](Idea* a, Idea* b) { 
            return a->createTime > b->createTime; 
        };
        priority_queue<Idea*, vector<Idea*>, decltype(createCmp)> createQ(createCmp);
        
        // 创建任务队列（按优先级、所需时间、创建时间、PM序号排序）
        auto taskCmp = [](Idea* a, Idea* b) {
            if (a->priority != b->priority)
                return a->priority < b->priority;
            if (a->duration != b->duration)
                return a->duration > b->duration;
            if (a->createTime != b->createTime)
                return a->createTime > b->createTime;
            return a->pmId > b->pmId;
        };
        priority_queue<Idea*, vector<Idea*>, decltype(taskCmp)> taskQ(taskCmp);
        
        // 初始化ideas
        for (int i = 0; i < p; i++) {
            Idea* idea = new Idea(i, ideas[i][0], ideas[i][1], ideas[i][2], ideas[i][3]);
            allIdeas.push_back(idea);
            createQ.push(idea);
        }
        
        // 程序员状态
        vector<int> programmerTime(m, 0);
        
        // 模拟时间流程
        int currentTime = 0;
        while (!createQ.empty() || !taskQ.empty()) {
            // 处理当前时间点的新idea
            while (!createQ.empty() && createQ.top()->createTime == currentTime) {
                taskQ.push(createQ.top());
                createQ.pop();
            }
            
            // 分配任务给空闲程序员
            for (int i = 0; i < m; i++) {
                if (programmerTime[i] > 0) {
                    programmerTime[i]--;
                    continue;
                }
                
                if (!taskQ.empty()) {
                    Idea* idea = taskQ.top();
                    taskQ.pop();
                    idea->finishTime = currentTime + idea->duration;
                    programmerTime[i] = idea->duration;
                }
            }
            
            currentTime++;
        }
        
        // 收集结果
        for (int i = 0; i < p; i++) {
            result[i] = allIdeas[i]->finishTime;
        }
        
        // 清理内存
        for (auto idea : allIdeas) {
            delete idea;
        }
        
        return result;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int n, m, p;
    cin >> n >> m >> p;
    
    vector<vector<int>> ideas(p, vector<int>(4));
    for (int i = 0; i < p; i++) {
        for (int j = 0; j < 4; j++) {
            cin >> ideas[i][j];
        }
    }
    
    Solution solution;
    vector<int> result = solution.solve(n, m, p, ideas);
    
    for (int time : result) {
        cout << time << endl;
    }
    
    return 0;
}

import java.util.*;

class Idea {
    int id;         // idea的序号
    int pmId;       // PM的序号
    int createTime; // 提出时间
    int priority;   // 优先级
    int duration;   // 所需时间
    int finishTime; // 完成时间
    
    public Idea(int id, int pmId, int createTime, int priority, int duration) {
        this.id = id;
        this.pmId = pmId;
        this.createTime = createTime;
        this.priority = priority;
        this.duration = duration;
        this.finishTime = -1;
    }
}

class Solution {
    public int[] solve(int n, int m, int p, int[][] ideas) {
        int[] result = new int[p];
        List<Idea> allIdeas = new ArrayList<>();
        
        // 创建idea生产队列（按创建时间排序）
        PriorityQueue<Idea> createQ = new PriorityQueue<>(
            (a, b) -> Integer.compare(a.createTime, b.createTime)
        );
        
        // 创建任务队列（按优先级、所需时间、创建时间、PM序号排序）
        PriorityQueue<Idea> taskQ = new PriorityQueue<>((a, b) -> {
            if (a.priority != b.priority)
                return Integer.compare(b.priority, a.priority);
            if (a.duration != b.duration)
                return Integer.compare(a.duration, b.duration);
            if (a.createTime != b.createTime)
                return Integer.compare(a.createTime, b.createTime);
            return Integer.compare(a.pmId, b.pmId);
        });
        
        // 初始化ideas
        for (int i = 0; i < p; i++) {
            Idea idea = new Idea(i, ideas[i][0], ideas[i][1], ideas[i][2], ideas[i][3]);
            allIdeas.add(idea);
            createQ.offer(idea);
        }
        
        // 程序员状态
        int[] programmerTime = new int[m];
        
        // 模拟时间流程
        int currentTime = 0;
        while (!createQ.isEmpty() || !taskQ.isEmpty()) {
            // 处理当前时间点的新idea
            while (!createQ.isEmpty() && createQ.peek().createTime == currentTime) {
                taskQ.offer(createQ.poll());
            }
            
            // 分配任务给空闲程序员
            for (int i = 0; i < m; i++) {
                if (programmerTime[i] > 0) {
                    programmerTime[i]--;
                    continue;
                }
                
                if (!taskQ.isEmpty()) {
                    Idea idea = taskQ.poll();
                    idea.finishTime = currentTime + idea.duration;
                    programmerTime[i] = idea.duration;
                }
            }
            
            currentTime++;
        }
        
        // 收集结果
        for (int i = 0; i < p; i++) {
            result[i] = allIdeas.get(i).finishTime;
        }
        
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int p = sc.nextInt();
        
        int[][] ideas = new int[p][4];
        for (int i = 0; i < p; i++) {
            for (int j = 0; j < 4; j++) {
                ideas[i][j] = sc.nextInt();
            }
        }
        
        Solution solution = new Solution();
        int[] result = solution.solve(n, m, p, ideas);
        
        for (int time : result) {
            System.out.println(time);
        }
        
        sc.close();
    }
}

from typing import List
from queue import PriorityQueue

class Idea:
    def __init__(self, id: int, pm_id: int, create_time: int, priority: int, duration: int):
        self.id = id                 # idea的序号
        self.pm_id = pm_id          # PM的序号
        self.create_time = create_time  # 提出时间
        self.priority = priority     # 优先级
        self.duration = duration     # 所需时间
        self.finish_time = -1        # 完成时间
    
    def __lt__(self, other):
        return self.create_time < other.create_time

class Solution:
    def solve(self, n: int, m: int, p: int, ideas: List[List[int]]) -> List[int]:
        result = [0] * p
        all_ideas = []
        
        # 创建idea生产队列（按创建时间排序）
        create_q = []
        
        # 初始化ideas
        for i in range(p):
            idea = Idea(i, ideas[i][0], ideas[i][1], ideas[i][2], ideas[i][3])
            all_ideas.append(idea)
            create_q.append(idea)
        
        # 按创建时间排序
        create_q.sort(key=lambda x: x.create_time)
        
        # 任务队列
        task_q = []
        
        # 程序员状态
        programmer_time = [0] * m
        
        # 模拟时间流程
        current_time = 0
        create_idx = 0
        
        while create_idx < len(create_q) or task_q:
            # 处理当前时间点的新idea
            while create_idx < len(create_q) and create_q[create_idx].create_time == current_time:
                task_q.append(create_q[create_idx])
                create_idx += 1
            
            # 按优先级排序任务队列
            task_q.sort(key=lambda x: (-x.priority, x.duration, x.create_time, x.pm_id))
            
            # 分配任务给空闲程序员
            for i in range(m):
                if programmer_time[i] > 0:
                    programmer_time[i] -= 1
                    continue
                
                if task_q:
                    idea = task_q.pop(0)
                    idea.finish_time = current_time + idea.duration
                    programmer_time[i] = idea.duration
            
            current_time += 1
        
        # 收集结果
        for i in range(p):
            result[i] = all_ideas[i].finish_time
        
        return result

def main():
    n, m, p = map(int, input().split())
    ideas = []
    for _ in range(p):
        ideas.append(list(map(int, input().split())))
    
    solution = Solution()
    result = solution.solve(n, m, p, ideas)
    
    for time in result:
        print(time)

if __name__ == "__main__":
    main()