贪心法（二）—— 区间调度、区间选点

本文主要是介绍贪心法（二）—— 区间调度、区间选点，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

区间调度

思路：

将结束时间按从小到大排序。要注意的是，每一项工作的开始时间与结束时间是一组，（不能分开排序）需要打包。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
public class Main {public static void main(String[] args) {		                Scanner sc = new Scanner(System.in);int n = sc.nextInt();   int []s = new int[n];int []t = new int[n];Job[] jobs = new Job[n]; //创建Job类型把s与t打包for(int i=0;i<n;i++){s[i] = sc.nextInt();}for(int i=0;i<n;i++){t[i] = sc.nextInt();}for(int i=0;i<n;i++){jobs[i] = new Job(s[i],t[i]);}Arrays.sort(jobs);int res = f(n,jobs);System.out.println(res);   }private static int f(int n, Job[] jobs) {	int y = jobs[0].t;int res=1;for(int i=1;i<n;i++){if(jobs[i].s >= y){res++;y = jobs[i].t;}}return res;}private  static class Job implements Comparable<Job>{int s;int t;public Job(int s,int t){this.s=s;this.t = t;}public int compareTo(Job other) {int x = this.t - other.t;if(x==0) return this.t - other.t;elsereturn x;}	}
}

区间选点 POJ1201

题目的大致意思是，给定n个闭区间，并且这个闭区间上的点都是整数，现在要求你使用最少的点来覆盖这些区间并且每个区间的覆盖的点的数量满足输入的要求点覆盖区间的数量。

输入：

第一行输入n，代表n个区间。

接下来的每行的第一个数代表区间起点，第二个数代表区间终点，第三个数代表这个区间必须要选取的点的数量。

输出：

输出最少的点的数量，这些最少的点要覆盖全部区间。

与区间调度类似，都是按照结束时间排序，都以结束时间为选取原则；
此题要使用一个数组来标识是否已选取，避免重复选取。

import java.util.Arrays;
import java.util.Scanner;
public class Main{public static void main(String[] args) {		                Scanner sc = new Scanner(System.in);int n = sc.nextInt();   Interval[] intervals = new Interval[n];//创建Interval类型把s,t与c打包for(int i=0;i<n;i++){intervals[i] = new Interval(sc.nextInt(),sc.nextInt(),sc.nextInt());}Arrays.sort(intervals);int max = intervals[n-1].t;int [] ans = new int[max+1]; //标识点是否被选中for(int i=0;i<n;i++){int s = intervals[i].s;int t = intervals[i].t;int c = intervals[i].c;int cnt = sum(ans,s,t);  //记录区间已标记点数量c-=cnt;   //还需标记点的个数while(c > 0){if(ans[t] == 0){ans[t] = 1;c--;t--;}else{t--;}} }System.out.println(sum(ans,intervals[0].s,max));}private static int sum(int[] ans, int s, int t) {int v = 0;for(int i = s;i <= t;i++){if(ans[i] == 1)v++;  }return v;}private  static class Interval implements Comparable<Interval>{int s;int t;int c;public Interval(int s,int t,int c){this.s = s;this.t = t;this.c = c;}public int compareTo(Interval other) {int x = this.t - other.t;if(x==0) return this.t - other.t;elsereturn x;}	}
}

问题

区间选点用上述方法会超时，可以用树状数组解决，后面补充。

这篇关于贪心法（二）—— 区间调度、区间选点的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---