**Dominoes(insert atmost k numbers and make maximum length of continuous number )

Dominoes

There are N dominoes arranged in a straight line. For each domino you know its coordinate, an integer value. It is guaranteed all the coordinates are distinct. You have another set of K dominoes. You should place these dominoes at integer coordinates in a way that will preserve the property that all the coordinates are distinct. You want to maximize the size of a subset of dominoes that are placed at consecutive coordinates.

Standard input

The first line contains two integer values N and K.

The second line contains N integer values, the coordinates of the initial dominoes.

Standard output

The output should contains a single value representing the size of the maximum subset of dominoes that can have consecutive coordinates.

Constraints and notes

• 1 ≤ N ≤ 100 000
• 1 ≤ K ≤ 100 000
• The coordinates of the dominoes are between 1 and 1 000 000

Input	Output	Explanation
8 4 1 2 3 4 10 11 14 15	8	It is optimal to place the dominoes at coordinates 12, 13, 16 and 17.

===========================EDITORIAL==================================

I DID THIS PROBLEM WITH SIMPLE SLIDING CONCEPT ..

FIRST OF ALL SORT THE NUMBERS , THAN  FIRST CALCULATE MAXIMUM  LENGTH IF START FORM THE FIRST NUMBER , NOW ONE OBSERVATION IS THAT IF WE START FORM INDEX 0 ANT WE CAN MAKE A CONTINUOUS NUMBER TILL INDEX 3( IN K OPERATIONS) THAN IF WE START FORM INDEX 1 THAN AT LEAST WE WILL REACH TILL INDEX 3 ( IN K OPERATIONS)..

   WITH THE HELP OF THIS PROPERTY WE CAN SOLVE THIS PROBLEM USING SLIDING WINDOW..

=============================CODE====================================

#include<bits/stdc++.h>

using namespace std;

typedef long long int lli;

#define ff first

#define ss second

#define mp make_pair

#define ph push_back

#define mod 1000000007

#define debug 0

vector<int>v[100010];

int main()

 {

 

  int n,kk;

   cin>>n>>kk;

   int last=0;

    int count=0;

   for(int i=0;i<n;i++)

     {

      int a;

       cin>>a;

          v[0].push_back(a);

   }

   int ans=0;

   sort(v[0].begin(),v[0].end());

  

     int k=0;

           int size=v[k].size();

            int l=0;

           int re=kk;

      for(int i=0;i<size;i++)

       {

        if(i!=0)

            {

           re+=v[k][i]-v[k][i-1]-1;

}

if(l<i)

                 {

              l=i;

              re=kk;

         }

         while(re>=0)

          {

          

            if(l+1==size)

             {

               ans=max(ans,v[k][l]+re-v[k][i]+1);

               re=0;

               break;

 }

          else if(re>=v[k][l+1]-v[k][l]-1)

           {

             re-=v[k][l+1]-v[k][l]-1;

             l+=1;

   }

   else

   {

     ans=max(ans,v[k][l]-v[k][i]+1+re);

     break;

   }

      }

}

cout<<ans<<endl;

 }

======================ANOTHER APPROACH ============================

WE CAN ALSO SOLVE THIS PROBLEM USING BINARY SEARCH 

SEE THE CODE 

#include<bits/stdc++.h>

using namespace std;

/*      my general mistakes that costed me a lot

          * check for overflows

          * check and mod and use int type variables where possible to avoid tles

          * while multiplying two variables whose value can exceed integer 

          limt make sure to typecase them

          * use scanf when you are not working with the best possible optimisation

          * return a value from a function that has a return type sometimes the 

          compiler may give the correct answer but there will be problem in the judge

          * be very cautious about uninitiaalised variables , infact never keep them

          or handle them properly*/

#define ff first

#define ss second

#define mp make_pair

#define pb push_back

#define ll long long int

#define pp pair<int,int> 

#define ve vector

#define mod 1000000007

/************************************CODE BEGINS HERE************************/

int h[2000010];

int main()

{

   

 int n;

 cin>>n;

 int k;

 cin>>k;

 int mx=0;

 for(int i=0;i<n;i++)

 {

  int aa;

     cin>>aa;

     mx=max(mx,aa+k);

     h[aa]++;

 }

 for(int i=1;i<=mx;i++)

 {

  h[i]+=h[i-1];

 }

 int res=0;

 for(int i=1;i<=mx;i++)

 {

            int low=1;

            int high=i;

            int ans=0;

            bool f=0;

            while(low<=high)

            {

                 if(low==high)

f=1;

int mid=(low+high)/2;

int len=i-mid+1;

int req=len-(h[i]-h[mid-1]);

// if(i==10)

// {

//   cout<<"mid "<<mid<<" "<<req<<endl;

// }

if(req<=k)

{

ans=(i-mid+1);

high=mid;

}

else low=mid+1;

if(f)

break;

  }

//   cout<<"for "<<i<<" "<<ans<<endl;

  res=max(ans,res);

 }

 cout<<res<<endl;

 return 0;

}