AFL (Australian Football League)

Here's my problem:

AFL

Input File: aflin.txt
File: aflout.txt
Time Limit: 1 second

It's football season, and the rush is on. You have the unfortunate job
of trying to arrange seating in the stadium for the horde of fans
phoning in to the ticket office.

Luckily you are only responsible for a single row of seats. For each
football fan who phones in with a booking for k people, you have to
find a continuous block of k empty seats in the row in which they can
sit. To save yourself the hassle of having to decide each time which
block of k empty seats to book, you decide upon the following
strategy.

Each time a fan phones in with a booking for k people, you find the
longest continuous sequence of empty seats in the row (if there is a
tie then you choose the leftmost longest sequence). You then book the
first k seats in this sequence (and hope that the sequence of empty
seats is long enough). These seats are then marked as taken, and you
move on to answer the next phone call.

As an example, consider a row of 10 seats numbered 1,2,,10. Say
that seats 3 and 8 have already been taken before you start making
bookings. The initial state of the row is illustrated in the following
diagram, where the shaded seats have already been taken.

Suppose that the first phone call is for a booking of size 1. The
longest continuous sequence of empty seats is from seats 4 to 7, so
you place the booking at the beginning of this sequence, claiming seat
4.

Suppose that the next request is for a booking of size 2. The longest
continuous sequence of empty seats is now from seats 5 to 7, so the
booking is made for seats 5 and 6.

Let the next request be another booking of size 1. There are now two
longest continuous sequences of empty seats, each of length two.
is from seats 1 to 2 and the other is from seats 9 to 10. You choose
the leftmost of these longest sequences and book seat 1.

And so on. After a few days of carrying out this procedure it is
becoming rather tedious, so you decide to write a computer program
that can carry it out for you. Grabbing your laptop and an AFL-branded
meat pie, you set to work.
Input

The first line of input will contain the single integer n representing
the total number of seats in the row (1 <= n <= 30,000). These seats
are numbered 1,2,,n from left to right.

The second line of input will contain the single integer t
representing the total number of seats that have already been taken (0
<= t <= n). Following this will be t lines, each containing the number
of a seat that has been taken (no two of these seat numbers will be
identical).

The next line of input will contain the single integer b representing
the total number of bookings that you must make (0 <= b <= n).
Following this will be b lines, each describing a single booking. Each
of these lines will contain a single integer k representing the number
of seats to be booked (1 <= k <= n). The bookings will be presented in
order from the first phone call to the last.


For each booking, your program should write a single line of output.
This line should contain a single integer describing the leftmost seat
that was booked.

You may assume that it is possible to successfully make all of the
requested bookings using the strategy described above.
Sample Input

The following sample data corresponds to the example discussed
earlier.

10
2
3
8
3
1
2
1

Sample

4
5
1

Here's my code so far

#include <stdio.h>

struct group* nextseat(struct group g[], int ngroups);
int main()
{
//
FILE* in = fopen("aflin.txt" , "r");
FILE* out = fopen("alfout.txt", "w");

int nseats, t, b;

fscanf(in, "%d", &nseats );
fscanf(in, "%d", &t );

int booked[t];
int i = 0;
for (; i < t; i++)
{
fscanf(in, "%d", &booked[i]);
}

fscanf(in, "%d", &b);
int bookings[b];

for (i = 0; i < b; i++)
{
fscanf(in, "%d", &bookings[i]);
}
//

/
/
i = 0; // what group we're up to
int j = 1; // what booked seat we're up to

struct group {
int length;
int fseat;
} g[nseats];

int ngroups = 0;
g[i].length = booked[i] - 1;
if (g[i].length 0)
{
g[i].fseat = 1;
++ngroups;
}
++i;

for (; i <= t - 1; i++)
{
g[i].length = booked[j] - booked[j-1] - 1;
if (g[i].length == 0)
{
;
}
else
{
++ngroups;
g[i].fseat = booked[j-1] + 1;
}
++j;
}

g[i].length = nseats - booked[j-1];
if (g[i].length 0)
{
g[i].fseat = booked[j-1] + 1;
++ngroups;
}

int k = 0;
for (; k < ngroups; k++)
printf("group[%d] length: %d fseat %d\n", k, g[k].length,
g[k].fseat);
/
/

int longest_length = 0;
int nlonglengroups = 0;
struct group* longlengroups[ngroups];

for (i = 0; i < ngroups; i++)
{
if (g[i].length longest_length)
{
longest_length = g[i].length;
}

/* if (g[i].length == longest_length)
{
longlengroups[nlonglengroups] = &g[i];
++nlonglengroups;
} */
}


for (i = 0; i < ngroups; i++)
{
if (g[i].length == longest_length)
{
longlengroups[nlonglengroups] = &g[i];
++nlonglengroups;
}
}

struct group* leftmostlonggroup = longlengroups[0];
for (i = 0; i < nlonglengroups; i++)
{
if (longlengroups[i]->fseat < leftmostlonggroup->fseat)
{
leftmostlonggroup = longlengroups[i];
}
}
printf("%d", leftmostlonggroup->fseat);

return 0;
}

For the bit from the last // to the return 0, how do I put that
into one loop? I've broken this part into three steps:

1. Find the longest length
2. Find the groups that have this 'longest length'
3. Find the group which has the longest length and is the leftmost (ie
with the lowest fseat)

I don't understand how to pack it into one loop.
And my tutor said this would work for maybe 80% of possible inputs but
would go over 1 second to output the other 20%. He said he'd tell me
how to use data structures when I start school, but what data
structure should I be using?

Bert wrote:
Guys this isn't spam. Are you not replying because you think this is
spam?
No, because you have a communication problem,
and it is not in your computer.

Can someone please tell me the pseudocode for this and how the came up
with it? I really can't do it.

Bert wrote:
Here's my problem:
>
AFL
>
Input File: aflin.txt
File: aflout.txt
Time Limit: 1 second
>
It's football season, and the rush is on. You have the unfortunate job
of trying to arrange seating in the stadium for the horde of fans
phoning in to the ticket office.
>
Luckily you are only responsible for a single row of seats. For each
football fan who phones in with a booking for k people, you have to
find a continuous block of k empty seats in the row in which they can
sit. To save yourself the hassle of having to decide each time which
block of k empty seats to book, you decide upon the following
strategy.
>
Each time a fan phones in with a booking for k people, you find the
longest continuous sequence of empty seats in the row (if there is a
tie then you choose the leftmost longest sequence). You then book the
first k seats in this sequence (and hope that the sequence of empty
seats is long enough). These seats are then marked as taken, and you
move on to answer the next phone call.
>
As an example, consider a row of 10 seats numbered 1,2,,10. Say
that seats 3 and 8 have already been taken before you start making
bookings. The initial state of the row is illustrated in the following
diagram, where the shaded seats have already been taken.
>
Suppose that the first phone call is for a booking of size 1. The
longest continuous sequence of empty seats is from seats 4 to 7, so
you place the booking at the beginning of this sequence, claiming seat
4.
>
Suppose that the next request is for a booking of size 2. The longest
continuous sequence of empty seats is now from seats 5 to 7, so the
booking is made for seats 5 and 6.
>
Let the next request be another booking of size 1. There are now two
longest continuous sequences of empty seats, each of length two.
is from seats 1 to 2 and the other is from seats 9 to 10. You choose
the leftmost of these longest sequences and book seat 1.
>
And so on. After a few days of carrying out this procedure it is
becoming rather tedious, so you decide to write a computer program
that can carry it out for you. Grabbing your laptop and an AFL-branded
meat pie, you set to work.
Input
>
The first line of input will contain the single integer n representing
the total number of seats in the row (1 <= n <= 30,000). These seats
are numbered 1,2,,n from left to right.
>
The second line of input will contain the single integer t
representing the total number of seats that have already been taken (0
<= t <= n). Following this will be t lines, each containing the number
of a seat that has been taken (no two of these seat numbers will be
identical).
>
The next line of input will contain the single integer b representing
the total number of bookings that you must make (0 <= b <= n).
Following this will be b lines, each describing a single booking. Each
of these lines will contain a single integer k representing the number
of seats to be booked (1 <= k <= n). The bookings will be presented in
order from the first phone call to the last.

>
For each booking, your program should write a single line of output.
This line should contain a single integer describing the leftmost seat
that was booked.
>
You may assume that it is possible to successfully make all of the
requested bookings using the strategy described above.
Sample Input
>
The following sample data corresponds to the example discussed
earlier.
>
10
2
3
8
3
1
2
1
>
Sample
>
4
5
1
>
Here's my code so far
>
#include <stdio.h>
>
struct group* nextseat(struct group g[], int ngroups);
int main()
{
//
FILE* in = fopen("aflin.txt" , "r");
FILE* out = fopen("alfout.txt", "w");
>
int nseats, t, b;
>
fscanf(in, "%d", &nseats );
fscanf(in, "%d", &t );
>
int booked[t];
int i = 0;
for (; i < t; i++)
{
fscanf(in, "%d", &booked[i]);
}
>
fscanf(in, "%d", &b);
int bookings[b];
>
for (i = 0; i < b; i++)
{
fscanf(in, "%d", &bookings[i]);
}
//
>
/
/
i = 0; // what group we're up to
int j = 1; // what booked seat we're up to
>
struct group {
int length;
int fseat;
} g[nseats];
>
int ngroups = 0;
g[i].length = booked[i] - 1;
if (g[i].length 0)
{
g[i].fseat = 1;
++ngroups;
}
++i;
>
for (; i <= t - 1; i++)
{
g[i].length = booked[j] - booked[j-1] - 1;
if (g[i].length == 0)
{
;
}
else
{
++ngroups;
g[i].fseat = booked[j-1] + 1;
}
++j;
}
>
g[i].length = nseats - booked[j-1];
if (g[i].length 0)
{
g[i].fseat = booked[j-1] + 1;
++ngroups;
}
>
int k = 0;
for (; k < ngroups; k++)
printf("group[%d] length: %d fseat %d\n", k, g[k].length,
g[k].fseat);
/
/
>
int longest_length = 0;
int nlonglengroups = 0;
struct group* longlengroups[ngroups];
>
for (i = 0; i < ngroups; i++)
{
if (g[i].length longest_length)
{
longest_length = g[i].length;
}
>
/* if (g[i].length == longest_length)
{
longlengroups[nlonglengroups] = &g[i];
++nlonglengroups;
} */
}
>
>
for (i = 0; i < ngroups; i++)
{
if (g[i].length == longest_length)
{
longlengroups[nlonglengroups] = &g[i];
++nlonglengroups;
}
}
>
struct group* leftmostlonggroup = longlengroups[0];
for (i = 0; i < nlonglengroups; i++)
{
if (longlengroups[i]->fseat < leftmostlonggroup->fseat)
{
leftmostlonggroup = longlengroups[i];
}
}
printf("%d", leftmostlonggroup->fseat);
>
return 0;
}
>
For the bit from the last // to the return 0, how do I put that
into one loop? I've broken this part into three steps:
>
1. Find the longest length
2. Find the groups that have this 'longest length'
3. Find the group which has the longest length and is the leftmost (ie
with the lowest fseat)
>
I don't understand how to pack it into one loop.
And my tutor said this would work for maybe 80% of possible inputs but
would go over 1 second to output the other 20%. He said he'd tell me
how to use data structures when I start school, but what data
structure should I be using?

Bert wrote:

Can someone please tell me the pseudocode for this and how the came up
with it? I really can't do it.

<snip>

Basically you should maintain two lists, one for booked seats and the
other free ones. For each request scan the free list for the largest
sized block greater than the request itself, deduct the appropriate
amount and add it to the booked list and update the free list.

Reading and writing the files should be pretty straightforward. Just
code to the specifications given.

Bert wrote:
It's football season, and the rush is on. You have the unfortunate job
of trying to arrange seating in the stadium for the horde of fans
phoning in to the ticket office.
>
Luckily you are only responsible for a single row of seats. For each
football fan who phones in with a booking for k people, you have to
find a continuous block of k empty seats in the row in which they can
sit. To save yourself the hassle of having to decide each time which
block of k empty seats to book, you decide upon the following
strategy.
>
Each time a fan phones in with a booking for k people, you find the
longest continuous sequence of empty seats in the row (if there is a
tie then you choose the leftmost longest sequence). You then book the
first k seats in this sequence (and hope that the sequence of empty
seats is long enough). These seats are then marked as taken, and you
move on to answer the next phone call.

Ignoring any actual coding questions here, the algorithm is seriously
broken. For any request to buy K seats, you want to find the _shortest_
run of available seats that still meets the request. If there is no
matching run, the allocation must fail (or be divided into two requests
and recurse), rather than potentially double-booking seats.

, you will sell a run of 10 seats to 10 people wanting 1 seat
each, then find yourself unable to fulfill an order for a 10-seat block
-- or worse, finding only single seats available and then double-booking
the next 9 seats.

I'd normally ignore that point, but this actually has implications for
more topical situations, like a memory allocator trying to decide which
of several available blocks would best meet a request.

S