Can this task be solved using only sorting?
Does the solution always exist?

I got wa5. I cant find my bug. please help to find my bug or
give me the test my prog fail

import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Locale;

public class Timus1105 {

    private static StreamTokenizer st;
    private static double l;
    private static int n;
    private static ArrayList<Interval> list;

    public static void main(String[] args) {
        Locale.setDefault(Locale.US);
        st = new StreamTokenizer(new InputStreamReader(System.in));
        l = - nextDouble() + nextDouble();
        n = nextInt();
        list = new ArrayList<Interval>();

        for (int i = 0; i < n; i++) {
            list.add(new Interval(nextDouble() , nextDouble(), i + 1));

        }
        Collections.sort(list);
        for (int i = 1; i < list.size() ; ) {
            if(list.get(i).r <= list.get(i - 1).r){
                list.remove(i);
            }
            else{
                if(i < list.size() - 1 && list.get(i).r < list.get(i + 1).r && list.get(i + 1).l <= list.get(i - 1).r){
                    list.remove(i);
                }
                else
                    i++;
            }
        }
        double sum1 = 0;
        double sum2 = 0;
        for (int i = 0; i < list.size(); i++) {
            if(i % 2 == 0){
                sum1 += list.get(i).r - list.get(i).l;
            }
            else{
                sum2 += list.get(i).r - list.get(i).l;
            }
        }


        for (int i = 0; i < list.size() - 1; i++) {
            double r = Math.min(list.get(i).r, list.get(i + 1).l);
            double l = Math.max(list.get(i + 1).l, list.get(i).r);
            list.get(i).r = r;
            list.get(i + 1).l = l;
        }

        double sum = 0;
        ArrayList<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < list.size(); i++) {
            double x = list.get(i).r - list.get(i).l;
            if(x > 0){
                sum += x;
                ans.add(list.get(i).i);
            }
        }

        if(sum1 > sum ){
            sum = sum1;
            ans.clear();
            for (int i = 0; i < list.size(); i+=2) {
                ans.add(list.get(i).i);
            }
        }
        if(sum1 > sum){
            sum = sum2;
            ans.clear();
            for (int i = 1; i < list.size(); i+=2) {
                ans.add(list.get(i).i);
            }
        }
        if(3 * sum >= 2 * l){
            System.out.println(ans.size());
            for (int i = 0; i < ans.size(); i++) {
                System.out.println(ans.get(i));
            }
        }
        else{
            System.out.println(list.size());
            for (int i = 0; i < list.size(); i++) {
                System.out.println(list.get(i));
            }
        }
    }

    static double nextDouble(){
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return st.nval;
    }

    static int nextInt(){
        try {
            st.nextToken();
        } catch (IOException e) {
            e.printStackTrace();
        }
        return (int) st.nval;
    }

    static class Interval implements Comparable<Interval>{
        double l, r;
        int i;

        Interval(double l1, double r1, int i1){
            l = l1;
            r = r1;
            i = i1;
        }

        @Override
        public int compareTo(Interval o) {
            int ret = (int) (this.l - o.l);
            if(ret == 0){
                ret = (int) (o.r - this.r);
            }
            return ret;
        }


    }
}

program ural;
var f,e,p,q:real;
    i,n,s,l,d,t:integer;
    a,b:array[1..10000]of real;
    u,k:array[1..10000]of integer;
    o:array[0..1]of real;
procedure heap;
  begin
    p:=a[s];
    q:=b[s];
    t:=k[s];
    d:=s shl 1;
    if(d<l)and((a[d]<a[d+1])or((a[d]=a[d+1])and(b[d]>b[d+1])))then
      inc(d);
    while(d<=l)and((p<a[d])or((p=a[d])and(q>b[d])))do
      begin
        a[s]:=a[d];
        b[s]:=b[d];
        k[s]:=k[d];
        s:=d;
        d:=s shl 1;
        if(d<l)and((a[d]<a[d+1])or((a[d]=a[d+1])and(b[d]>b[d+1])))then
          inc(d);
      end;
    a[s]:=p;
    b[s]:=q;
    k[s]:=t;
  end;
begin
  assign(input,'observe.in');
  assign(output,'observe.out');
  reset(input);
  rewrite(output);
  readln(f,e);
  readln(n);
  for i:=1 to n do
    begin
      k[i]:=i;
      readln(a[i],b[i]);
    end;
  l:=n;
  for i:=n shr 1 downto 1 do
    begin
      s:=i;
      heap;
    end;
  for i:=n downto 2 do
    begin
      t:=k[i];
      k[i]:=k[1];
      k[1]:=t;
      p:=a[i];
      a[i]:=a[1];
      a[1]:=p;
      p:=b[i];
      b[i]:=b[1];
      b[1]:=p;
      s:=1;
      l:=i-1;
      heap;
    end;
  u[1]:=1;
  t:=1;
  for i:=2 to n do
    if b[u[t]]<b[i] then
      begin
        while(t>1)and(a[i]<=b[u[t-1]])do
          dec(t);
        inc(t);
        u[t]:=i;
      end;
  for i:=1 to t do
    o[i and 1]:=b[u[i]]-a[u[i]];
  f:=(e-f)*2/3;
  if o[1]>=f then
    begin
      t:=(t+1) shr 1;
      writeln(t);
      for i:=0 to t-1 do
        writeln(k[u[i shl 1 or 1]]);
    end
  else
    if o[0]>=f then
      begin
        t:=t shr 1;
        writeln(t);
        for i:=1 to t do
          writeln(k[u[i shl 1]]);
      end
    else
      begin
        writeln(t);
        for i:=1 to t do
          writeln(k[u[i]]);
      end;
end.

I think, testset is not enough.
Please, add such test:

#include <cstdio>

int main()
{
  int N = 10000;
  double k = 1.5;

  printf("%lf %lf\n", 0.0, N * (k + 1));
  printf("%d\n", N);
  for (int i = 0; i < N; i++)
    printf("%d %.1lf\n", i, i + 1.5 * N);
  return 0;
}

If the test is:
0.0 20.0
2
0.0 12.0
8.0 20.0
If I coloured both of them, what is the summary time?
I'll appreciate your help.

Please, tell me, what can be in it?

I'm sure that my algorythm is correct. It's complexity is O
(n log n), because I use quicksort, and then 2 linear
procedures. Why do I get TimeLimitExceed? Is it possible
not to use sorting?

Could anybody give me any hints about solution.
There was posted one algorithm but it is wrong -
there is a counter-example for it. So, anybody who
has AC, tell me please how to solve it.

I got WA on test5.

i think i've known the algorithm.
but why wa?

program p1105;

const
  maxn=10000;
  zero=0;

var
  a,b:array [1..maxn] of real;
  code,t:array [1..maxn] of longint;
  n,i,top:longint;
  time,start,finish:real;

  procedure qksort(p,q:longint);
  var
    r,kcode,i,j:longint;
    ka,kb:real;
  begin
    r:=random(q-p+1)+p;
    ka:=a[r]; kb:=b[r]; kcode:=code[r];
    a[r]:=a[p]; b[r]:=b[p]; code[r]:=code[p];
    i:=p; j:=q;
    while i<j do
    begin
      while (i<j) and ((ka<a[j]-zero) or (ka<=a[j]+zero) and (kb>=b
[j]-zero))
        do dec(j);
      a[i]:=a[j]; b[i]:=b[j]; code[i]:=code[j];
      while (i<j) and ((a[i]<ka-zero) or (a[i]<=ka+zero) and (b[i]
>=kb-zero))
        do inc(i);
      a[j]:=a[i]; b[j]:=b[i]; code[j]:=code[i];
    end;
    a[i]:=ka; b[i]:=kb; code[i]:=kcode;
    if p<i-1 then qksort(p,i-1);
    if i+1<q then qksort(i+1,q);
  end;

begin
  read(start,finish);
  read(n);
  for i:=1 to n do
  begin
    read(a[i],b[i]);
    code[i]:=i;
  end;

  if n=0 then
  begin
    writeln(0);
    exit;
  end;

  qksort(1,n);
  t[1]:=1; top:=1;
  for i:=2 to n do
    if b[i]>b[t[top]]+zero then
    begin
      inc(top);
      t[top]:=i;
    end;

  time:=0;
  for i:=1 to top do
    if odd(i) then time:=time+b[t[i]]-a[t[i]];
  if time>=2/3*(finish-start) then
  begin
    writeln((top+1) div 2);
    for i:=1 to top do
      if odd(i) then writeln(code[t[i]]);
    exit;
  end;

  time:=0;
  for i:=1 to top do
    if not(odd(i)) then time:=time+b[t[i]]-a[t[i]];
  if time>=2/3*(finish-start) then
  begin
    writeln(top div 2);
    for i:=1 to top do
      if not(odd(i)) then writeln(code[t[i]]);
    exit;
  end;

  writeln(top);
  for i:=1 to top do writeln(code[t[i]]);
end.