【刷题篇】贪心算法（二）

文章目录

• 找出工作所需最短时间
• 活动选择
• 无重叠区间

找出工作所需最短时间

某工厂有n个独立的作业，由m台相同的机器进行加工处理。作业i所需的加工时间为ti，任何作业在被处理时不能中断，也不能进行拆分处理。现厂长请你给他写一个程序:算出n个作业由m台机器加工处理的最短时间
第一行T(1测试数据。每组测试数据的第一行分别是整数n，m(1<=n<=10000,1<=m<=100)，接下来的一行是n个整数ti (1<=t<=100)。

#include
#include
#include

using namespace std;

//n个工作时间是n[i]，m台机器所需最短时间

struct myclass {
	bool operator() (int i, int j) { return (i < j); }
} myobject;

int besttimes(vector<int>& works,int m)
{
	//如果工作件数少于机器数据量的话，就直接取单个工作的最大时间
	int numworks = works.size();
	//将数组进行排序
	sort(works.begin(), works.end(), myobject);

	int* machine = new int[m]{0};
	if (numworks <= m)
	{
		return works[numworks-1];
	}
	else
	{
		//分配机器，找最先结束工作的,升序所以要使用大到小
		for (int i = numworks - 1; i >= 0; i--)
		{   //这里记录一下
			int finish = 0;
			int machinetimes = machine[finish];
			for (int j = 0; j < m; j++)
			{
				if (machine[j] < machinetimes)
				{
					finish = j;
					machinetimes = machine[j];
				}
			}
			machine[finish] += works[i];
		}
	}
	//排序找哪台机器时间最长
	sort(machine, machine + m, myobject);
	return machine[m - 1];
}

//10 5 3 7 2 1
int main()
{
	vector<int> works = {10,5,3,7,2,1};
	int m = 0;
	cin >> m ;
	int times=besttimes(works,m);
	cout << times;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

活动选择

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

#include
#include
#include

using namespace std;

//这里的思想不能由每个活动的开始时间进行比较
//也不能由每个活动的持续时间进行比较
//因为上面的题解是要求出一天当中最多可以进行多少活动
//由此上面的情况会出现时间冲突问题
//所以按结束的时间进行比较是最合理的

struct cmp
{
	bool operator()(vector<int>& a,vector<int>& b)
	{
		return a[1] < b[1];
	}
}cmp;

int most_activity(vector<vector<int>>& greed)
{
	sort(greed.begin(), greed.end(), cmp);
	int signtail = 0;
	int cnt = 0;
	for (auto& e : greed)
	{
		if (e[0] >= signtail)
		{
			signtail = e[1];
			cnt++;
		}
	}
	return cnt;
}

int main()
{
	vector<vector<int>> greed = { {2,5} ,{3,4},{1,6},{5,8},{5,7},{3,9},{7,10} };
	int size= most_activity(greed);
	cout << size << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

无重叠区间

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

方法一是和上面的题思路是一样的，就是在最后的结果改一下

class Solution {
public:
    struct cmp
    {
        bool operator()(vector<int>& a,vector<int>&b)
        {
            return a[1]<b[1];
        }
    }cmp;

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int num=1;
        int i=0;
        for(int j=1;j<intervals.size();j++)
        {
            if(intervals[j][0]>=intervals[i][1])
            {
                num++;
                i=j;
            }
            
        }
        return intervals.size()-num;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第二种方法是考虑三种情况，删除一个就记录一下
上面的方法是将区间的尾进行排序，而下面的是将区间的头进行排序，分为下面的三种情况看图片

class Solution {
public:
    struct cmp
    {
        bool operator()(vector<int>& a,vector<int>&b)
        {
            return a[0]<b[0];
        }
    }cmp;

    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        sort(intervals.begin(),intervals.end(),cmp);
        int num=0;
        int i=0;
        for(int j=1;j<intervals.size();j++)
        {
            if(intervals[j][0]>=intervals[i][1])
            {
                i=j;
            }
            else
            {
                if(intervals[j][0]<intervals[i][1]&&intervals[j][1]<=intervals[i][1])
                {
                    i=j;
                    num++;
                }
                else
                {
                    num++;
                }
            }
        }
        return num;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36