贪心算法OJ刷题(2)

多机调度问题

题目描述

某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为 $t_i$ ，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序：算出n个作业由m台机器加工处理的最短时间。

输入：第一行T（1<T<100)表示有T组测试数据。每组测试数据的第一行分别是整数n，m（1<=n<=10000，
1<=m<=100），接下来的一行是n个整数ti（1<=t<=100)。输出：所需的最短时间。

解题思路

该题较难求出最优解，但可以利用贪心策略设计出次优解。

分情况讨论：1、当n<=m时，只要将作业分给每一个机器即可；

2、当n>m时，首先将n个作业从大到小排序，然后依此顺序将作业分配给空闲的处理机。也就是说从剩下的作业中，选择需要处理时间最长的，给最先结束的机器去执行，然后依次选择处理时间次长的，直到所有的作业全部处理完毕，或者机器不能再处理其他作业为止。

如果我们每次是将需要处理时间最短的作业分配给空闲的机器，那么可能就会出现其它所有作业都处理完了只剩所需时间最长的作业在处理的情况，这样势必效率较低。

#pragma once
#include<iostream>
#include<algorithm>
#include <vector>
using namespace std;

bool cmp(const int& x, const int& y)
{
	return x > y;
}

int findMax(const vector<int>& machines)
{
	int max = machines[0];
	for (int i = 1; i < machines.size(); ++i)
	{
		if (machines[i] > max) max = machines[i];
	}
	return max;
}

int greedStrategy(vector<int>& works, vector<int>& machines)
{
	//按照作业时间从大到小排序 sort默认升序
	sort(works.begin(), works.end(), cmp);
	int workNum = works.size();
	int machineNum = machines.size();
	// 作业数如果小于机器数，直接返回最大的作业时间
	int minimalTime = 0;
	if (workNum <= machineNum) {
		minimalTime = works[0];
	}
	else
	{
		for (int i = 0; i < workNum; ++i)
		{
			int id = 0;
			// 第一个任务给第一台机器
			int tmp = machines[id];
			// 从剩余机器中选择作业时间最小的
			for (int j = 1; j < machineNum; ++j)
			{
				if (machines[j] < tmp)
				{
					id = j;
					tmp = machines[j];
				}
			}
			// 将当前作业交给最小的机器执行
			machines[id] += works[i];
		}
		minimalTime = findMax(machines);
	}
	return minimalTime;
}

活动选择

题目描述

有n个需要在同一天使用同一个教室的活动a1, a2, …, an，教室同一时刻只能由一个活动使用。每个活动a[i]都有一个开始时间s[i]和结束时间f[i]。一旦被选择后，活动a[i]就占据半开时间区间[s[i],f[i])。如果[s[i],f[i])和[s[j],f[j])互不重叠，a[i]和a[j]两个活动就可以被安排在这一天。求使得尽量多的活动能不冲突的举行的最大数量。

解题思路

选择持续时间最短的活动（其开始和结束时间都无法让其他活动在同一天举办）或者选择活动时间最早开始的活动（其持续时间可能最长）都无法得到最优解。

直入主题，每次选择活动结束时间最早的活动 $a_i$ ，只要它的活动开始时间不早于上一个活动的结束时间，就可以选择该活动。故将活动结束时间进行升序处理，然后遍历活动开始时间，选开始时间最早的活动。

#pragma once
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

int ActivitySelect(vector<int>& start, vector<int>& end)
{
	map<int, int> map;
	int ret = 0;
	for (size_t i = 0; i < start.size(); ++i)
	{
		map.insert(pair<int, int>(end[i], start[i]));
	}
	int maxtime = 0;
	for (auto& kv : map)
	{
		//如果该活动的开始时间不小于目前的结束时间，就可以选择
		if (maxtime <= kv.second)
		{
			//更新最晚结束时间
			maxtime = kv.first;
			ret++;
		}		
	}
	return ret;
}

最多可以参加的会议数

题目描述

给你一个数组 events，其中 events[i] = [startDayi, endDayi] ，表示会议 i 开始于 startDayi ，结束于 endDayi 。你可以在满足 startDayi <= d <= endDayi 中的任意一天 d 参加会议 i 。注意，一天只能参加一个会议。请你返回你可以参加的最大会议数目。

解题思路

此题是在区间内任选一天参加即可。比如[[1,2], [1,2]]，可以在第一天参加第一个会议，在第2天参加第二个会议。

用unorder_map，第一个参数int保存会议的开始时间，第二个参数vector保存在同一天开始的会议的结束时间。再用priority_queue对同一天开始的会议的结束时间做升序排列，每次选择最早结束的会议。

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int maxDay = 0;
        unordered_map<int, vector<int>> day;
        for(vector<int>& event : events)
        {
            //遍历得到最晚的结束时间
            if(maxDay < event[1]) maxDay = event[1];
            //开始时间相同的会议，对应的结束时间存在一个数组里
            day[event[0]].push_back(event[1]);
        }

        int ret = 0;
        //构建一个小顶堆
        priority_queue<int, vector<int>, greater<int>> q;
        for(int i = 1; i <= maxDay; ++i)
        {
            //第1天到第maxDay天之间，看哪天有会议
            if(day.find(i) != day.end())
            {
                //记录会议的结束时间，升序排列
                for(int end_time : day[i])
                {
                    q.push(end_time);
                }
            }
            // 删除队列里结束时间小于i的会议：因为它们已经结束了，无法再选择
            while(!q.empty() && q.top() < i)
            {
                q.pop();
            }
            // 每次选择一个最早结束的会议，然后pop掉
            if(!q.empty())
            {
                q.pop();
                ret++;
            }
        }
        return ret;
    }
};

无重叠区间

题目描述

给定一个区间的集合 intervals ，其中 intervals[i] = [starti, endi] 。返回需要移除区间的最小数量，使剩余区间互不重叠。

解题思路

和活动选择这道题思路一样，只不过返回结果不一样。

也可以按照左区间来递增排序，选择右区间更小的那个（可以为后序的预留更大的空间）

//沿用活动选择的思路
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        return a[1] < b[1];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();//总共有n个区间
        //按照右区间进行升序排列
        sort(intervals.begin(), intervals.end(), cmp);
        int max_right = INT_MIN;
        int can = 0;
        for(int i = 0; i < n; ++i)
        {
            //如果左区间大于等于最大右区间
            //表示两个区间无重叠
            if(intervals[i][0] >= max_right)
            {
                max_right = intervals[i][1];
                can++;
            }
        }
        return n - can;
    }
};
//以左区间来作升序排序
class Solution {
public:
    static bool cmp(const vector<int>& a, const vector<int>& b)
    {
        return a[0] < b[0];
    }
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        int n = intervals.size();//总共有n个区间
        //按照左区间进行升序排列
        sort(intervals.begin(), intervals.end(), cmp);
        
        int end = intervals[0][0], prev = 0, count = 0;        
		for (int i = 1; i < intervals.size(); i++) 
        {
            //如果当前区间的左区间 大于等于 累积区间的右区间，表示无重叠
            if (intervals[i][0] >= intervals[prev][1]) 
            {
                prev = i;
            } 
            //表示两个区间有重叠
            else 
            {                
                //选择结束时间早的那个右区间
                if (intervals[prev][1] > intervals[i][1]) 
                {
                    prev = i;
                }
                count++;
            }
		}
        return count;
    }
};

注意：二维数组vector<vector<int>>要用算法函数sort（默认是按第一个元素升序排列），用到的比较函数是cmp，其中的单个元素是vector<int>。

bool cmp(const vector<int>& kv1, const vector<int>& kv2)
{
    return kv1[1] < kv2[1];
}
int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(), intervals.end(), cmp);
}