3, Java - rextester

3

//'main' method must be in a class 'Rextester'.
//openjdk version '11.0.5'

import java.util.*;
import java.lang.*;

class Rextester
{  
    static class Helper
    {
       int x;
       int y;
        
        public Helper(int x,int y)
        {
          this.x=x;
          this.y=y;
        }
    }
   static class Compare
    {
         static void compare(Helper b[], int n)
       {
            Arrays.sort(b, new Comparator<Helper>()
              {
                  public int compare(Helper p1, Helper p2)
                  {
                    if(p1.x == p2.x)
                         return p1.y - p2.y;
                      else
                          return p1.x - p2.x; 
                  }
              }
                            
        );
    }
    }
    static int minhelp(Helper b[], int n)
    {
        int ans=0;
        int l=0;
        int max=0,i;
        while(n>max)
        {
            for( i=0;i<n;i++)
            {
                if(l >= b[i].x && max < b[i].y)
                    max=b[i].y;
            }
            if(l == max)
                return -1;
            ans++;
            l=max;
        }
        return ans;
    }
   
    public static void main(String args[])
    {
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int a[]=new int[n];
        for(int i=0;i<n;i++)
            a[i]=sc.nextInt();
        
        Helper b[]=new Helper[n];
        int i,j,x,y;
        for(i=0;i<n;i++)
        {
            //j=0;
            x=(i-a[i]);
            y=(i + a[i]);
            if(  x < 0 || x > n)
            {
               // System.out.print(x+ " ");
                
                x=0;
            }
             else
             {
                 // System.out.print(x+ " ");
                  x=i-a[i];
             }
               
             if( y > n || y < 0)
             {
                // System.out.print(y+ " ");
                 y=0;
             }
            else
            {
              //  System.out.print(y+ " ");
                y=i + a[i];
            }
            b[i]=new Helper(x,y);
            // System.out.println();
        }
       /* System.out.println();
        System.out.println();
        for(i=0;i<n;i++)
        {
           System.out.print(b[i].x + " " +b[i].y);
           System.out.println();
       }   */
        Compare z= new Compare();
        z.compare(b,n);
        System.out.println("After sorting");
        for(i=0;i<n;i++)
        {
           System.out.print(b[i].x + " " +b[i].y);
           System.out.println();
       }
        
        int ans=minhelp(b,n);
        System.out.println(ans);
    }
}


run \| edit \| history \| help	0