什么是贪心？贪心就是自然智慧的算法。
介绍
比如说你在公司里面，产品经理说，我们要把充值用户服务好，他给我们充值了，我们就有现金流了，就能渡过难关，这是贪心算法。
产品经理又说，优质的客户是可以给我们推广，让更多人知道我们，从而带动用户流入，这也是贪心算法。
也就是说，贪心算法，就是你每一步做出的角色，是当前状况下看来，是最好的决策。当你做完决策后，情况会变，然后在变化的情况中，继续选下当前最好的决策，一步步的去处理，每一步都做当下最好的决策，这就是贪心算法。
我们在计算机中所说的贪心算法，难点在于你要证明当先做出的决策，是全局最优解的。如果你每一步都是最优解，那么到最后你的贪心算法是有效的，如果你某一步并非最优解，你的贪心算法就是无效的。
举个例子：
如果一个数组中，有N个大于1的正数，无序的，你如何获得最大的分数和？规则如下：
- 第一个挑出来的数 乘 1 ，就是你的分数1。
- 第二个挑出来的数 乘 2 ，就是你的分数2。
- 第三个挑出来的数 乘 3 ，就是你的分数3。
然后把分数1+分数2+分数3的总和
比如[1,6,3]
....
你如何在这样的规则下，找到最优解？，也就是最大的乘积和。
你需要把数组排序下，然后第一个数乘1，第二个数乘2，第三个数乘3等等，依次相加。比如是最优解。
也就是 1*1+2*3+3*6的组合，一定是最优解，排序后，越到后面数越大，而index也是越大，两个大数相乘，肯定是大数。
这就是简单的 贪心算法，因为每一步都是最优解，如果是 1*1+2*6*3*3，第一步贪心算法是对的，但是第二步就开始错了，所以这个贪心算法是错误的。
所以，贪心算法，并没有一个公式让你去套用，它取决于你平时的阅历和经验，还有你的数学能力。因为它难点在于证明局部最有利的标准可以得到全局最优解。
例子
字符串数组字典序问题
先介绍一个概念：
字典序：就是两个字符串，当做单词放入字典中，谁在前面谁最小。 当然，我们的规则是a-z的顺序规则。如果位数相同，则按照规则来，如果位数不相同，则短的在后面补0,0就是比a更小的数。比如两个单词，一个是abc，一个是bs，明显是abc单词比bs单词字典序最小，因为a在前面，又比如abc和abd，abc字典序最小，因为c比d小。
题目： 给定一个由字符串组成的数组，必须把所有的字符串拼接起来，返回所有可能的拼接结果中，字典序最小的结果。
例如，给定字符串数组[ac,bk,sc,ket]，拼出来字典序最小的结果就是acbkketsc，当然，单词不能拆开。
func concatenateStringGreedy(strs []string) string {
sort.Slice(strs, func(i, j int) bool {
return strs[i]+strs[j] < strs[j]+strs[i] // 这里的每一步，都是比较两个字符串的大小
})
return strings.Join(strs, "")
}
会议室安排问题
题目：公司中一些项目要占用会议室，会议室不能同时容纳两个项目的宣讲，给出项目的开始世间和结束时间，要求写一个go程序来安排宣讲的会议，要求会议室进行的宣讲次数最多，返回最多的宣讲场次。
比如开会时间为：{6, 7},{8, 9},{7, 8},{7, 10},{6, 9}} ，最优的选项就是三场，{6 7} {7 8} {8 9}。
这其实是一个很典型的贪心问题，有好几种解决思路：
- 1：按照开始时间来排序，错误
- 2：按照开会时间最短的来，错误
- 3：按照开会时间最长的来，错误
- 4：按照结束时间来排序，正确。
由此可见，贪心算法就是各种模式，然后得出每一步都是最优解。
func arrange(meets []meet) {
// 根据结束时间排序
sort.Slice(meets, func(i, j int) bool {
return meets[i].endTime < meets[j].endTime
})
fmt.Println(meets)
fmt.Println("--------------")
arrangeMeets := []meet{meets[0]}
currentEnd := meets[0].endTime
// 如果结束时间小于下一场的开始时间，则安排
for i := 1; i < len(meets); i++ {
if currentEnd <= meets[i].startTime {
arrangeMeets = append(arrangeMeets, meets[i])
currentEnd = meets[i].endTime
}
}
fmt.Println(arrangeMeets)
}
