ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1303. Минимальное покрытие

Показать все сообщения Спрятать все сообщения

Memory limit exceeded Test#8 Andrey 16 май 2012 19:15
Help!!!


import java.util.*;
public class Ll {
    public static class Line implements Comparable{
        int a,b;
        Line(int x, int y){
            a = x;
            b = y;
        }
        public int compareTo(Object obj){
            Line tmp =  (Line)obj;
            if (this.b>tmp.b) return 1;
            if (this.b<tmp.b) return -1;
            return 0;
        }
    }


    public static void main(String args[]){
        Scanner stream = new Scanner(System.in);
        short M  = stream.nextShort();
        ArrayList<Line> arL = new ArrayList<Line>();
        arL.add(new Line(stream.nextInt(), stream.nextInt()) );
        while(true){
            int a=stream.nextInt(), b=stream.nextInt();
            if ((a==0)&&(b==0)) break;

            if((b>0)&&(a<M))
                for (int i=0;i<arL.size();i++){
                    if  ((arL.get(i).a>=a) && (arL.get(i).b<=b)){
                        arL.set(i,new Line(a,b)) ;}
                    else  {if (!((arL.get(i).a<=a) && (arL.get(i).b>=b)))
                    arL.add(new Line(a,b));} break;
                }
            }


        if(arL.size()==0) {
            System.out.println("No solution");
            return;
        }
        arL.trimToSize();
        Collections.sort(arL);
         ArrayList<Integer> arV= new ArrayList<Integer>();
        int i=arL.size()-1,F =0;
        while ((i>=0)&&(arL.get(i).b>0)){


            if (arL.get(i).a<=F){
                F=arL.get(i).b;
                arV.add(i);
                i = arL.size();
            }

            if (F>=M){
                System.out.println(arV.size());
                for (int g= 0;g<arV.size();g++){
                    System.out.println(arL.get(arV.get(g)).a + " "+ arL.get(arV.get(g)).b);

                }
                return;

            }
            i--;
        }
        System.out.println("No solution");
    }


}