Problem Statement |
| |
You work in a company that produces measuring devices. The software for each device is stored in reprogrammable memory. To program a device, you must connect it to a personal computer and transmit data to the device's reprogrammable memory through a serial interface. Your task is to make this process as efficient as possible.
You are given two int[]s offset and size. Each corresponding pair of elements in offset and size describes a piece of data that must be transmitted to the device. The i-th piece of data consists of size[i] consecutive bytes that must be written starting at the address in offset[i]. To successfully program a device, you must write every piece of the given data. Memory addresses that are not referenced in this data are not important - so you can write anything to those addresses, or write nothing at all to them.
Data is transmitted from the computer to the device through packets. Each packet can contain a maximum of maxData bytes of consecutive data that will be written to a specified memory address. Return the minimum possible total number of packets required to transmit all of the given data to the device.
|
| |
Definition |
| | | Class: | ProgrammingDevice | | Method: | minPackets | | Parameters: | int[], int[], int | | Returns: | int | | Method signature: | int minPackets(int[] offset, int[] size, int maxData) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | Assume that the reprogrammable memory of the measuring device is infinitely large. |
| |
Constraints |
| - | offset will contain between 1 and 50 elements, inclusive. |
| - | offset and size will contain the same number of elements. |
| - | Each element of offset will be between 0 and 1,000,000,000, inclusive. |
| - | Each element of size will be between 1 and 1,000,000,000, inclusive. |
| - | None of the pieces of data described by offset and size will overlap. |
| - | maxData will be between 1 and 2,000,000,000, inclusive. |
| |
Examples |
| 0) | |
| | {0, 10, 20, 30} | {8, 5, 3, 11} | 6 |
| Returns: 6 | | Send 15 bytes starting from offset 0 in 3 packets.
Only 13 of those 15 bytes are meaningful. There are 2 dummy bytes starting from offset 8.
Then, send 3 bytes starting from offset 20 in 1 packet.
Finally, send 11 bytes starting from offset 30 in 2 packets.
A total of 6 packets are sent.
|
|
|
| 1) | |
| | {0, 10, 20, 30} | {8, 2, 3, 11} | 6 |
| Returns: 5 | | Send 12 bytes starting from offset 0 in 2 packets.
Then, send 3 bytes starting from offset 20 in 1 packet.
Finally, send 11 bytes starting from offset 30 in 2 packets.
A total of 5 packets are sent.
|
|
|
| 2) | |
| | |
| 3) | |
| | {77, 7777, 777} | {700, 70000, 7000} | 1 |
| Returns: 77700 | |
|
| 4) | |
| | {0,1000000000} | {1000000000,1000000000} | 2000000000 |
| Returns: 1 | |
|
| 5) | |
| | {0,1000000000} | {1000000000,1000000000} | 1 |
| Returns: 2000000000 | |
|