题目 1 · Free Response
9 分This question involves the `ServerCluster` class, which manages compute tasks across worker nodes in a data center. Tasks can be scheduled on one of several worker nodes, numbered $1$ through $10$. Each node operates over a 24-hour daily cycle, divided into $24$ one-hour time slots numbered $0$ through $23$.
A requested computing task has a duration, which is the number of consecutive hours the task requires. In order for a task to be scheduled on a given node, the node must have a block of consecutive available hours that is at least equal to the requested duration. Scheduled tasks must start and end on the same worker node within the 24-hour cycle (hours $0$ through $23$).
The `ServerCluster` class contains two helper methods: `isNodeAvailable` and `reserveNode`. You will write two additional methods of the `ServerCluster` class.
```java
public class ServerCluster
{
/**
* Returns true if worker node nodeNum is available for task execution
* during hour; returns false otherwise.
* Preconditions: 1 <= nodeNum <= 10; 0 <= hour <= 23
/
private boolean isNodeAvailable(int nodeNum, int hour)
{ / implementation not shown */ }
/**
* Marks the block of hours on nodeNum that begins at startHour and
* lasts for duration hours as reserved.
* Preconditions: 1 <= nodeNum <= 10; 0 <= startHour <= 23;
* 1 <= duration <= 24;
* startHour + duration <= 24
/
private void reserveNode(int nodeNum, int startHour, int duration)
{ / implementation not shown */ }
/**
* Searches nodeNum for the first block of duration consecutive available
* hours during the day (hours 0 to 23), as described in part (a).
* Returns the starting hour of the block if found, or -1 if no such
* block is found.
* Preconditions: 1 <= nodeNum <= 10; 1 <= duration <= 24
/
public int findContinuousBlock(int nodeNum, int duration)
{ / to be implemented in part (a) */ }
/**
* Searches worker nodes from startNode to endNode, inclusive, for a block
* of duration consecutive available hours, as described in part (b).
* If such a block is found, calls reserveNode to reserve the block and
* returns true; otherwise, returns false.
* Preconditions: 1 <= startNode <= endNode <= 10; 1 <= duration <= 24
/
public boolean scheduleTask(int startNode, int endNode, int duration)
{ / to be implemented in part (b) */ }
// There may be instance variables, constructors, and methods that are not shown.
}
```
(a) Write the `findContinuousBlock` method, which searches `nodeNum` for the first block of available hours that is `duration` hours long. If such a block is found, `findContinuousBlock` returns the starting hour of the block. Otherwise, `findContinuousBlock` returns `-1`. The `findContinuousBlock` method uses the helper method `isNodeAvailable`, which returns `true` if the node is available at a given hour and `false` otherwise. No hours should be marked as reserved as a result of calling `findContinuousBlock`.
Complete the `findContinuousBlock` method:
```java
/**
* Searches nodeNum for the first block of duration consecutive available
* hours during the day (hours 0 to 23), as described in part (a).
* Returns the starting hour of the block if found, or -1 if no such
* block is found.
* Preconditions: 1 <= nodeNum <= 10; 1 <= duration <= 24
*/
public int findContinuousBlock(int nodeNum, int duration)
```
(b) Write the `scheduleTask` method, which searches worker nodes from `startNode` to `endNode`, inclusive, for the earliest available block of `duration` consecutive hours on the lowest-numbered node. If such a block is found, `scheduleTask` calls `reserveNode` to reserve the block on that node and returns `true`. If no such block is found on any of the specified nodes, `scheduleTask` returns `false`.
Assume that `findContinuousBlock` works as intended, regardless of what you wrote in part (a). You must use `findContinuousBlock` and `reserveNode` appropriately in order to receive full credit.
Complete the `scheduleTask` method:
```java
/**
* Searches worker nodes from startNode to endNode, inclusive, for a block
* of duration consecutive available hours, as described in part (b).
* If such a block is found, calls reserveNode to reserve the block and
* returns true; otherwise, returns false.
* Preconditions: 1 <= startNode <= endNode <= 10; 1 <= duration <= 24
*/
public boolean scheduleTask(int startNode, int endNode, int duration)
```
A requested computing task has a duration, which is the number of consecutive hours the task requires. In order for a task to be scheduled on a given node, the node must have a block of consecutive available hours that is at least equal to the requested duration. Scheduled tasks must start and end on the same worker node within the 24-hour cycle (hours $0$ through $23$).
The `ServerCluster` class contains two helper methods: `isNodeAvailable` and `reserveNode`. You will write two additional methods of the `ServerCluster` class.
```java
public class ServerCluster
{
/**
* Returns true if worker node nodeNum is available for task execution
* during hour; returns false otherwise.
* Preconditions: 1 <= nodeNum <= 10; 0 <= hour <= 23
/
private boolean isNodeAvailable(int nodeNum, int hour)
{ / implementation not shown */ }
/**
* Marks the block of hours on nodeNum that begins at startHour and
* lasts for duration hours as reserved.
* Preconditions: 1 <= nodeNum <= 10; 0 <= startHour <= 23;
* 1 <= duration <= 24;
* startHour + duration <= 24
/
private void reserveNode(int nodeNum, int startHour, int duration)
{ / implementation not shown */ }
/**
* Searches nodeNum for the first block of duration consecutive available
* hours during the day (hours 0 to 23), as described in part (a).
* Returns the starting hour of the block if found, or -1 if no such
* block is found.
* Preconditions: 1 <= nodeNum <= 10; 1 <= duration <= 24
/
public int findContinuousBlock(int nodeNum, int duration)
{ / to be implemented in part (a) */ }
/**
* Searches worker nodes from startNode to endNode, inclusive, for a block
* of duration consecutive available hours, as described in part (b).
* If such a block is found, calls reserveNode to reserve the block and
* returns true; otherwise, returns false.
* Preconditions: 1 <= startNode <= endNode <= 10; 1 <= duration <= 24
/
public boolean scheduleTask(int startNode, int endNode, int duration)
{ / to be implemented in part (b) */ }
// There may be instance variables, constructors, and methods that are not shown.
}
```
(a) Write the `findContinuousBlock` method, which searches `nodeNum` for the first block of available hours that is `duration` hours long. If such a block is found, `findContinuousBlock` returns the starting hour of the block. Otherwise, `findContinuousBlock` returns `-1`. The `findContinuousBlock` method uses the helper method `isNodeAvailable`, which returns `true` if the node is available at a given hour and `false` otherwise. No hours should be marked as reserved as a result of calling `findContinuousBlock`.
Complete the `findContinuousBlock` method:
```java
/**
* Searches nodeNum for the first block of duration consecutive available
* hours during the day (hours 0 to 23), as described in part (a).
* Returns the starting hour of the block if found, or -1 if no such
* block is found.
* Preconditions: 1 <= nodeNum <= 10; 1 <= duration <= 24
*/
public int findContinuousBlock(int nodeNum, int duration)
```
(b) Write the `scheduleTask` method, which searches worker nodes from `startNode` to `endNode`, inclusive, for the earliest available block of `duration` consecutive hours on the lowest-numbered node. If such a block is found, `scheduleTask` calls `reserveNode` to reserve the block on that node and returns `true`. If no such block is found on any of the specified nodes, `scheduleTask` returns `false`.
Assume that `findContinuousBlock` works as intended, regardless of what you wrote in part (a). You must use `findContinuousBlock` and `reserveNode` appropriately in order to receive full credit.
Complete the `scheduleTask` method:
```java
/**
* Searches worker nodes from startNode to endNode, inclusive, for a block
* of duration consecutive available hours, as described in part (b).
* If such a block is found, calls reserveNode to reserve the block and
* returns true; otherwise, returns false.
* Preconditions: 1 <= startNode <= endNode <= 10; 1 <= duration <= 24
*/
public boolean scheduleTask(int startNode, int endNode, int duration)
```
查看答案详解收起答案详解
解题
### Part (a) Implementation
```java
public int findContinuousBlock(int nodeNum, int duration)
{
int consecutive = 0;
for (int hour = 0; hour < 24; hour++)
{
if (isNodeAvailable(nodeNum, hour))
{
consecutive++;
if (consecutive == duration)
{
return hour - duration + 1;
}
}
else
{
consecutive = 0;
}
}
return -1;
}
```
Alternative Solution for Part (a):
```java
public int findContinuousBlock(int nodeNum, int duration)
{
for (int startHour = 0; startHour <= 24 - duration; startHour++)
{
boolean isAvailable = true;
for (int h = 0; h < duration; h++)
{
if (!isNodeAvailable(nodeNum, startHour + h))
{
isAvailable = false;
}
}
if (isAvailable)
{
return startHour;
}
}
return -1;
}
```
---
### Part (b) Implementation
```java
public boolean scheduleTask(int startNode, int endNode, int duration)
{
for (int node = startNode; node <= endNode; node++)
{
int startHour = findContinuousBlock(node, duration);
if (startHour != -1)
{
reserveNode(node, startHour, duration);
return true;
}
}
return false;
}
```
```java
public int findContinuousBlock(int nodeNum, int duration)
{
int consecutive = 0;
for (int hour = 0; hour < 24; hour++)
{
if (isNodeAvailable(nodeNum, hour))
{
consecutive++;
if (consecutive == duration)
{
return hour - duration + 1;
}
}
else
{
consecutive = 0;
}
}
return -1;
}
```
Alternative Solution for Part (a):
```java
public int findContinuousBlock(int nodeNum, int duration)
{
for (int startHour = 0; startHour <= 24 - duration; startHour++)
{
boolean isAvailable = true;
for (int h = 0; h < duration; h++)
{
if (!isNodeAvailable(nodeNum, startHour + h))
{
isAvailable = false;
}
}
if (isAvailable)
{
return startHour;
}
}
return -1;
}
```
---
### Part (b) Implementation
```java
public boolean scheduleTask(int startNode, int endNode, int duration)
{
for (int node = startNode; node <= endNode; node++)
{
int startHour = findContinuousBlock(node, duration);
if (startHour != -1)
{
reserveNode(node, startHour, duration);
return true;
}
}
return false;
}
```
评分标准
### Part (a) `findContinuousBlock` (5 points)
1. Iteration: Loops over hours in a day (0 to 23 or up to `24 - duration + 1`) without bounds errors. (1 point)
2. Helper method call: Calls `isNodeAvailable` with `nodeNum` and an integer representing the hour in the correct order. (1 point)
3. Tracking contiguous blocks: Maintains an accumulator/counter or boolean flag tracking consecutive available hours and resets correctly when an unavailable hour is encountered. (1 point)
4. Length check: Checks whether the contiguous block reaches the specified `duration`. (1 point)
5. Return values: Correctly calculates and returns the starting hour of the first qualifying block, and returns `-1` if no suitable block is found. (1 point)
### Part (b) `scheduleTask` (4 points)
6. Node loop: Traverses nodes from `startNode` through `endNode` inclusive without bounds errors. (1 point)
7. Method calls: Calls `findContinuousBlock(node, duration)` and `reserveNode(node, startHour, duration)` with appropriate parameters and correct order. (1 point)
8. Guard condition: Checks that the returned starting hour from `findContinuousBlock` is valid (`!= -1` or `>= 0`) before attempting reservation. (1 point)
9. Algorithm completion: Reserves the block on the lowest-numbered available node, immediately returns `true`, and returns `false` if all nodes are checked without finding a block. (1 point)
1. Iteration: Loops over hours in a day (0 to 23 or up to `24 - duration + 1`) without bounds errors. (1 point)
2. Helper method call: Calls `isNodeAvailable` with `nodeNum` and an integer representing the hour in the correct order. (1 point)
3. Tracking contiguous blocks: Maintains an accumulator/counter or boolean flag tracking consecutive available hours and resets correctly when an unavailable hour is encountered. (1 point)
4. Length check: Checks whether the contiguous block reaches the specified `duration`. (1 point)
5. Return values: Correctly calculates and returns the starting hour of the first qualifying block, and returns `-1` if no suitable block is found. (1 point)
### Part (b) `scheduleTask` (4 points)
6. Node loop: Traverses nodes from `startNode` through `endNode` inclusive without bounds errors. (1 point)
7. Method calls: Calls `findContinuousBlock(node, duration)` and `reserveNode(node, startHour, duration)` with appropriate parameters and correct order. (1 point)
8. Guard condition: Checks that the returned starting hour from `findContinuousBlock` is valid (`!= -1` or `>= 0`) before attempting reservation. (1 point)
9. Algorithm completion: Reserves the block on the lowest-numbered available node, immediately returns `true`, and returns `false` if all nodes are checked without finding a block. (1 point)