- package main;
- import java.util.ArrayList;
- import java.util.Collections;
- import java.util.Comparator;
- import java.util.List;
- import java.util.Random;
- public class Main {
- /**
- * 测试
- */
- public static void main(String[] args) {
- // 1.随机构造一批任务
- List<Pair<Integer>> inputList = new ArrayList<Pair<Integer>>();
- Random rand = new Random();
- for (int n=0; n<20; ++n) {
- Integer left = rand.nextInt(100);
- Integer right = left + rand.nextInt(100) + 1;
- Pair<Integer> pair = new Pair<Integer>(left, right);
- inputList.add(pair);
- }
- // 将任务列表按结束时间排序(也就是根据right字段进行排序)
- sortByRight(inputList);
- printPairList(inputList);
- // 执行算法
- List<Pair<Integer>> outputList = algorithm(inputList);
- System.out.println();
- printPairList(outputList);
- }
- /**
- * 贪心算法
- * @param inputList
- * @return 使数量最多的任务方案
- */
- public static <T extends Comparable<T>> List<Pair<T>> algorithm(List<Pair<T>> inputList) {
- if (null==inputList || inputList.size()==0 || inputList.size()==1) {
- return inputList;
- }
- sortByRight(inputList);
- List<Pair<T>> outputList = new ArrayList<Pair<T>>();
- int last = 0;
- outputList.add(inputList.get(last));
- int intputSize = inputList.size();
- for (int m=1; m<intputSize; ++m) {
- Pair<T> nextPair = inputList.get(m);
- T nextLeft = nextPair.getLeft();
- Pair<T> lastOutPair = inputList.get(last);
- T lastRight = lastOutPair.getRight();
- int flag = nextLeft.compareTo(lastRight);
- if (flag >= 0) {
- outputList.add(nextPair);
- last = m;
- }
- }
- return outputList;
- }
- /**
- * 对传入的List<Pair<T>>对象进行排序,使Pair根据right从小到大排序。
- * @param inputList
- */
- private static <T extends Comparable<T>> void sortByRight(List<Pair<T>> inputList) {
- CompareByRight<T> comparator = new CompareByRight<T>();
- Collections.sort(inputList, comparator);
- }
- /**
- * 打印一个List<Pair<T>>对象。
- * @param inputList
- */
- private static <T extends Comparable<T>> void printPairList(List<Pair<T>> inputList) {
- for (Pair<T> pair : inputList) {
- System.out.println(pair.toString());
- }
- }
- }
- /**
- * 根据Pair.right比较两个Pair。用于Conlections.sort()方法。
- * @param <T>
- */
- class CompareByRight<T extends Comparable<T>> implements Comparator<Pair<T>> {
- @Override
- public int compare(Pair<T> o1, Pair<T> o2) {
- T r1 = o1.getRight();
- T r2 = o2.getRight();
- int flag = r1.compareTo(r2);
- return flag;
- }
- }
- /**
- * 代表一个任务对象。有点装逼用模板来写了。left表示开始时间,right表示结束时间。
- * @param <T>
- */
- class Pair<T extends Comparable<T>> {
- private T left;
- private T right;
- public Pair(T left, T right) {
- this.left = left;
- this.right = right;
- }
- @Override
- public String toString() {
- return "[left=" + left.toString() + ',' + "right=" + right.toString() + ']';
- }
- public T getLeft() {
- return left;
- }
- public void setLeft(T left) {
- this.left = left;
- }
- public T getRight() {
- return right;
- }
- public void setRight(T right) {
- this.right = right;
- }
- }
- //该片段来自于http://www.codesnippet.cn/detail/151020136422.html
来源: http://www.codesnippet.cn/detail/151020136422.html