贪心--HDU2037--不相交区间问题

不念不忘少年蓝@ 2022-05-24 04:07 170阅读 0赞

# 不相交区间问题    #

题目大意：小墨喜欢看电视，他会事先查看喜欢看得电视节目的转播时间，然后合理安排，以看到尽量多的完整节目。

输入格式：输入多个实例，每个实例的第一行只有1个整数n（n<=100）,然后是n行，每行2个数据S,E,分别表示节目开始和结束的时间。

输出格式：输出能完整看到的电视节目的个数。

输入样例： 12
    
    1 3
    
    3 4
    
    0 7
    
    3 8
    
    15 19
    
    15 20
    
    10 15
    
    8 18
    
    6 12
    
    5 10
    
    4 14
    
    2 9
    
    输出样例：
    5

分析：

先对节目的时间进行排序，排序后有e1<=e2<=e3............那么就来讨论一下s1与s2。。。。

当s1>s2时，显然选s1更为合算

当s1<s2时

x2>y1时，先选s1再选s2

x2<=y1时，相交了，只能选1个，如果选择了s2区间，显然与下一个时段相交的更多，所以选s1才是明智的。

总的来说：就是第一个都选s1就是最合理的。

代码如下：

package 贪心;
    
    import java.util.Arrays;
    import java.util.Scanner;
    
    public class 不想交区间问题 {
    
    	public static void main(String[] args) {
    		// TODO Auto-generated method stub
    		Scanner in = new Scanner(System.in);
    		while(in.hasNext()){
    			int n = in.nextInt();  
    			if(n==0)
    				break;
    			Jiemu[] jie = new Jiemu[n];
    			for(int i = 0;i<n;i++){
    				jie[i] = new Jiemu(in.nextInt(),in.nextInt());
    			}
    			Arrays.sort(jie);
    //			for(int i = 0;i<n;i++){
    //				System.out.println(jie[i].toString());
    //			}
    			int ee;
    			ee = jie[0].e;
    			int max = 1;
    			for(int i = 1;i<n;i++){
    				if(ee<=jie[i].s){
    					max++;
    					ee = jie[i].e;
    				}
    			}
    			System.out.println(max);
    		}
    	}
    
    }
    class Jiemu implements Comparable<Jiemu>{
    	int s ;
    	int e;
    	public Jiemu(int s, int e) {
    		super();
    		this.s = s;
    		this.e = e;
    	}
    	@Override
    	public int compareTo(Jiemu o) {
    		// TODO Auto-generated method stub
    		if(this.e>o.e)
    			return 1;
    		else if(this.e<o.e)
    			return -1;
    		else
    			return 0;
    	}
    	@Override
    	public String toString() {
    		return "Jiemu [s=" + s + ", e=" + e + "]";
    	}
    	
    }