Problem1580--内存分配之首次适应算法

1580: 内存分配之首次适应算法

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 21  Solved: 5
[Submit] [Status] [Web Board] [Creator:]

Description

首次适应算法优先利用内存中低址部分的空闲分区,把起始地址最小的连续空闲空间分配给任务。
现在有一块空闲的内存空间[0,m-1],请使用首次适应算法对到来的n个指令进行分配和释放空间。
内存里可以存储多个ID相同的任务,但是回收指令只回收最先分配的那个任务。

Input

第一行输入指令条数n(1<=n<=200)和内存空间大小m(1<=m<=1000)。
接下来n行,每行输入两个整数x y,x代表任务的ID,y代表任务x需要分配的空间。
若y=-1,则回收第一个ID等于x的任务的空间。

Output

1.若空间分配成功,输出 allocate task x at [l,r] 代表为任务x分配了空间[l,r]
2.若空间分配失败,输出 allocation failed
3.若回收空间成功,输出 free [l,r] 代表回收了任务x的空间[l,r]
4.若未找到需回收的任务,输出 not found

Sample Input

8 10
1 5
2 7
3 3
1 -1
3  3
2 -1
4 1
4 2

Sample Output

allocate task 1 at [0,4]
allocation failed
allocate task 3 at [5,7]
free [0,4]
allocate task 3 at [0,2]
not found
allocate task 4 at [3,3]
allocate task 4 at [8,9]

Source/Category