首页 > 专题系列 > Java解POJ > POJ 1716 Integer Intervals [解题报告] Java
2013
11-10

POJ 1716 Integer Intervals [解题报告] Java

Integer Intervals

问题描述 :

An integer interval [a,b], a < b, is a set of all consecutive integers beginning with a and ending with b.

Write a program that: finds the minimal number of elements in a set containing at least two different integers from each interval.

输入:

The first line of the input contains the number of intervals n, 1 <= n <= 10000. Each of the following n lines contains two integers a, b separated by a single space, 0 <= a < b <= 10000. They are the beginning and the end of an interval.

输出:

Output the minimal number of elements in a set containing at least two different integers from each interval.

样例输入:

4
3 6
2 4
0 2
4 7

样例输出:

4

解题代码:

//* @author: [email protected]
import java.io.*;
import java.util.*;
public class Main
{
 public static void main(String[] args) throws NumberFormatException, IOException
 {
	InputStreamReader is=new InputStreamReader(System.in);
	BufferedReader in=new BufferedReader(is);
	int a=Integer.parseInt(in.readLine());
	int ans=2,i;
	my[] arr=new my[a];
	String[] ss;
	for(i=0;i< a;i++)
	{
         ss=in.readLine().split(" ");
	  int x=Integer.parseInt(ss[0]);
	  int y=Integer.parseInt(ss[1]);
	  arr[i]=new my(x,y);
	 }
	 Arrays.sort(arr);
	 int x=arr[0].b,y=x-1;
	 for(i=1;i< a;i++)
	 {
	  if(y>=arr[i].a){}
	  else if(x>=arr[i].a)
	  {
		y=x;
		x=arr[i].b;
		ans++;
	   }
	   else
	   {
		x=arr[i].b;
		y=x-1;
		ans+=2;
	    }
	   }
	System.out.printf("%d\n",ans);
  }
}
class my implements Comparable< my>
{
	public int a,b;
	public my(int x,int y)
	{
		a=x;
		b=y;
	}
	public int compareTo(my o) {
		return b-o.b;
	}
}

  1. Excellent Web-site! I required to ask if I might webpages and use a component of the net web website and use a number of factors for just about any faculty process. Please notify me through email regardless of whether that would be excellent. Many thanks