The Sports Stadium

Problem code: STADIUM

All submissions for this problem are available.

The bustling town of Siruseri has just one sports stadium. There are a number of schools, colleges, sports associations, etc. that use this stadium as the venue for their sports events.

Anyone interested in using the stadium has to apply to the Manager of the stadium indicating both the starting date (a positive integer S) and the length of the sporting event in days (a positive integer D) they plan to organise. Since these requests could overlap it may not be possible to satisfy everyone.

It is the job of the Manager to decide who gets to use the stadium and who does not. The Manager, being a genial man, would like to keep as many organisations happy as possible and hence would like to allocate the stadium so that maximum number of events are held.

Suppose, for example, the Manager receives the following 4 requests:

Event No. Start Date Length
125
297
3156
493

He would allot the stadium to events 1, 4 and 3. Event 1 begins on day 2 and ends on day 6, event 4 begins on day 9 and ends on day 11 and event 3 begins on day 15 and ends on day 20. You can verify that it is not possible to schedule all the 4 events (since events 2 and 3 overlap and only one of them can get to use the stadium).

Your task is to help the manager find the best possible allotment (i.e., the maximum number of events that can use the stadium).

Input format

The first line of the input will contain a single integer N (N 100000) indicating the number of events for which the Manager has received a request. Lines 2,3,...,N+1 describe the requirements of the N events. Line i+1 contains two integer Si and Di indicating the starting date and the duration of event i. You may assume that 1 Si 1000000 and 1 Di 1000.

Output format

Your output must consist of a single line containing a single integer M, indicating the maximum possible number of events that can use the stadium.

Example:

Sample input:

4
2 5
9 7
15 6
9 3

Sample output:

3
Author: admin
Date Added: 28-07-2009
Time Limit: 2 - 3 sec
Source Limit: 50000 Bytes
Languages: ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC


Comments

@admin: I am confident that

imrankane2005 @ 16 Jan 2010 12:55 AM

@admin: I am confident that my solution for this one must be correct. Can you please help me to get the case where I am getting WA.

Even I feel the same as

sppraveen @ 16 Jan 2010 01:28 AM

Even I feel the same as Imran. I believe my algorithm is right but I was getting WA when I tried sometime back. So just curious if this is some other data issue on your side

Yes, either the problem

triplem @ 16 Jan 2010 02:50 AM

Yes, either the problem statement is wrong, or the data is wrong.

To get accepted you'll need to have an output of 1, not 2, for a case like this:

2
1 1
2 1

i.e., you need to allow for a gap of one day between events.

@Stephen Merriman -: Thanx

imrankane2005 @ 16 Jan 2010 02:07 PM

@Stephen Merriman -: Thanx that was really helpfull :)

Thanks Stephen. That worked.

sppraveen @ 16 Jan 2010 06:12 PM

Thanks Stephen. That worked. This should ideally be taken care by admin in either responding or fixing the problem statement. I tried long back getting WA. Admin fix this.

I solved this problem and i'm

gopikrish2000 @ 27 Mar 2010 01:56 PM

I solved this problem and i'm getting correct results but when submitting its giving runtimeerror. Also i didnt use lot of memory in it . ny1 help me.

If you are getting a runtime

triplem @ 27 Mar 2010 02:54 PM

If you are getting a runtime exception then you clearly haven't solved the problem.

I ran a very simple case testing your code on maximal input numbers, and it threw an exception. Should have been one of the first test cases to check ;)

My code is even working on

devendermishra @ 25 Sep 2010 08:03 PM

My code is even working on the test cases mentioned here.

i.e.

2

1 2

2 1

It gives output 1.

And the alogrithm used here is fine.

And it is fine for sample test case.

Still I am getting Wrong Answer.

What else I need to check?

@admin - I'm pretty sure that

anmol_gulati @ 2 Oct 2010 08:23 PM

@admin -

I'm pretty sure that my algorithm is correct...Its working fine on my PC..Its also giving the right output for the test case - 1

1 1

2 1

But I'm getting a runtime error on the codechef compiler.....PLEASE HELP ME!!!

@admin: some codes submitted

vishsri616 @ 18 Aug 2011 01:08 AM
@admin: some codes submitted in java, c++ and RUBY exceeded 3 seconds time still their codes were accepted but mine wasn't??

@admin: code is doing fine on

vipul4vb @ 23 Mar 2012 04:05 PM
@admin: code is doing fine on http://ideone.com/dIgJn.. You both are using same compiler, then why its showing runtime error???????????????????????????????????

SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:

HELP

Program should read from standard input and write to standard output. After you submit a solution you can see your results by clicking on the [My Submissions] tab on the problem page. Below are the possible results:

 

  • Accepted Your program ran successfully and gave a correct answer. If there is a score for the problem, this will be displayed in parenthesis next to the checkmark.
  • Time Limit Exceeded Your program was compiled successfully, but it didn't stop before time limit. Try optimizing your approach.
  • Wrong Answer Your program compiled and ran succesfully but the output did not match the expected output.
  • Runtime Error Your code compiled and ran but encountered an error. The most common reasons are using too much memory or dividing by zero. For the specific error codes see the help section.
  • Compilation Error Your code was unable to compile. When you see this icon, click on it for more information.

    • If you are still having problems, see a sample solution here.

CodeChef is a global programming communityCodeChef hosts online programming competitions