题解 P1803 【凌乱的yyy】

孤独的观测者 · 2017-12-11 12:41:15 · 题解

TreeSet简直是算法神器

思路比较简单

-1. 结束早的放前面

-2. 同样时间结束的就看开始时间

-3. 然后直接遍历这个集合加过去就行了

代码如下

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.sql.Time;
import java.util.Comparator;
import java.util.Iterator;
import java.util.TreeSet;

public class Main
{

    public static void main(String[] args) throws NumberFormatException, IOException
    {
        int last=-1;
        int sum=0;
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int N=Integer.parseInt(bufferedReader.readLine());
        TreeSet<p> treeSet=new TreeSet<>(new comparaab());
        for (int i = 0; i < N; i++)
        {
            String[] strings=bufferedReader.readLine().split(" ");
            treeSet.add(new p(Integer.parseInt(strings[0]),Integer.parseInt(strings[1])));
        }
        for (Iterator iterator = treeSet.iterator(); iterator.hasNext();)
        {
            p p = (p) iterator.next();
            if(p.begintime<last)
            {
                continue;
            }
            last=p.endtime;
            sum++;
        }
        System.out.println(sum);
    }

}
class p
{
    int begintime;
    int endtime;

    public p(int order, int time)
    {
        super();
        this.begintime = order;
        this.endtime = time;
    }

}

class comparaab implements Comparator<p>
{

    @Override
    public int compare(p o1, p o2)
    {
        if(o1.endtime==o2.endtime)
        {
            return o1.begintime-o2.begintime;
        }
        return o1.endtime-o2.endtime;
    }
}