algorithm - How to increment all values in an array interval by a given amount -

-

suppose have array of length l. given n intervals(i,j) , have increment values between a[i] , a[j].which data structure suitable given operations?
intervals known beforehand.

break intervals start , end indexes: s_i,e_i i-th interval starts including s_i , ends excluding e_i

sort s_i-s array s sort e_i-s array e

set increment 0 start linear scan of input , add increment everyone, in each loop if next s_i current index increment increment if next e_i index decement increment

inc=0 s=<priorityqueue of interval startindexes> e=<priorityqueue of interval endindexes> for(i=0;i<n;i++){   if( inc == 0 ){     // skip adding zeros     i=min(s.peek(),e.peek())   }   while( s.peek() == ) {     s.pop();     inc++;   }   while( e.peek() == ) {     e.pop();     inc--;   }   a[i]+=inc; }

complexity(without skipping nonincremented elements): o(n+m*log(m)) // m number of intervals if n>>m it's o(n)

complexity when skipping elements: o( min( n , \sum length(i_i) ) ), length(i_i)=e_i-s_i


Comments

Post a Comment

Popular posts from this blog

java - Run a .jar on Heroku -

-
i trying run .jar file on heroku, , can't find instructions anywhere on how this. have read wants me compile uploading heroku. possible, , if is, how this? if helps, trying run minecraft craftbukkit server, , don't have pom.xml file yet. you didn't provide details i'll try give , people reaches question way it. first of all, create heroku account , create heroku application (assumed have done that). second, need generate application jar , upload heroku. so, open terminal , install heroku cli (assuming unix terminal): $ sudo npm install -g heroku-cli you need have npm , nodejs installed, can check link: https://www.digitalocean.com/community/tutorials/how-to-install-node-js-on-ubuntu-16-04 once done that, can use npm update node version acceptable heroku-cli: $ sudo npm install -g n $ sudo n 7.10.0 and run: $ sudo npm install -g heroku-cli in order deploy jars, need install deploy plugin: $ sudo heroku plugins:install heroku-cli-deploy ...
Read more

java - Jtable duplicate Rows -

-
Image
when add new rows in jtable duplicate rows many times this method update jtable public final void tableaucomande(){ ((defaulttablemodel)tabcommande.getmodel()).getdatavector().clear(); session s=hibernateutil.getsessionfactory().opensession(); criteria cr1= s.createcriteria(commande.class); list <commande> lcs=cr1.list() ; criteria cr2= s.createcriteria(lignecommande.class); list <lignecommande> lck=cr2.list() ; if(lcs.size()!=0 && lck.size()!=0) { (commande lc:lcs) { for(lignecommande lig:lck){ ((defaulttablemodel)tabcommande.getmodel()).addrow(new object[]{ lc.getid_cmd(),lc.getnumcmd(),lc.getdate_cmd(),lc.getclient().getnomprenom(), lig.getproduit().getlib_prd(),lig.getquantite(),lig.getproduit().getid_prd() }); } } // tabcommande.setrowselectioninterval(tabcommande.getrowcount()-1,tabcommande.getrowcount()-1); } } this code add add data rows displaye...
Read more

validation - How to pass paramaters like unix into windows batch file -

-
i need pass various parameters .cmd file unix format file.cmd -configuration=value -source=value -flag but, try this: startlocal @echo off cls setlocal set cmdline=%* set configuration= set source= set badargs= set validation= goto main :splitargs echo splitargs(%*) if "%*" neq "" ( /f "tokens=1,2,* delims== " %%i in ("%*") call :assignkeyvalue %%i %%j & call :splitargs %%k ) goto :eof :assignkeyvalue echo assignkeyvalue(%1, %2) if /i %1==-configuration ( set configuration=%2 ) else if /i %1==-source ( set source=%2 ) else ( rem append unrecognised [key,value] badargs echo unknown key %1 set badargs=%badargs%[%1, %2] ) goto :eof :validate echo validating set validation=fail if defined configuration ( echo -configuration ok if defined source ( echo -source ok if not defined badargs ( set validation=success ) ) ) goto :eof :main cl...
Read more