定义
贪心算法又叫做贪婪算法，它在求解某个问题是，总是做出眼前最大利益。
特点
- 局部最优解
- 通过局部最优推出全局最优
习题
- 某天早上公司领导找你解决一个问题，明天公司有N个同等级的会议需要使用同一个会议室，现在给你这个N个会议的开始和结束时间，你怎么样安排才能使会议室最大利用？即安排最多场次的会议？
会议时间：0点~9点 | 8点~10点 | 10点~12点 | 8点到~20点
思考：
这里先给出解决方案：以结束时间按从小到大排序，就能得出最优解。
首先为什么开始选择最小的9点而不是10点，由于一天只有24个小时，开始选择9点意味着后面还剩15个小时安排其他会议，而选择10点后面只剩14个小时安排会议，显然15个小时安排更多会议的可能性比14个小时安排更多会议的可能性要大，因此证明开始选择越小的结束时间越好。这里就是它的贪心策略。
同理可得，当确认第一个之后，后面要选的只要选择开始时间>=前面会议的结束时间&&结束时间更小的那个，因为结束时间更小，给后面预留安排会议的时间越大嘛。以上。
代码
public class Meeting implements Comparable<Meeting> { public int number; public int startTime; public int endTime; public Meeting(int number, int startTime, int endTime) { this.number = number; this.startTime = startTime; this.endTime = endTime; } @Override public int compareTo(Meeting o) { if (endTime > o.endTime) return 1; return -1; } @Override public String toString() { return "Meeting{" + "number=" + number + ", startTime=" + startTime + ", endTime=" + endTime + '}'; } public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int next = scanner.nextInt(); List<Meeting> meetings = new ArrayList<>(); for (int i = 1; i <= next; i++) { int startTime = scanner.nextInt(); int endTime = scanner.nextInt(); meetings.add(new Meeting(i, startTime, endTime)); } meetings.sort(null); System.out.println(meetings); System.out.println("==============="); int curTime = 0; for (Meeting meeting : meetings) { if(meeting.startTime>=curTime){ System.out.println(meeting); curTime = meeting.endTime; } } } }
