titok
BAN USER
- if it only contains intervals from the same calendar day
- if hourly granularity is good enough solution
and you don't need to sort the array (that would make it O(n*log(n))), because you don't use the sortedness of the array later, so without sorting you are done in O(n) [assuming that finding the maximum of the 24 slots is O(1) as it's independent from n]
void copy(byte[] dst, int dstFrom, byte[] src, int n) {
for (int s = 0, d=dstFrom; s < n; s++, d++) {
dst[d] = src[s];
}
}
byte[] Read(int sizeInBytes) {
byte[] buffer = new byte[sizeInBytes];
int read = 0, needToRead = sizeInBytes;
byte[] block;
while (needToRead >= 256) {
block = ReadFromDisk();
copy(buffer, read, block, 256);
read += 256;
needToRead -= 256;
}
if (needToRead>0) {
block = ReadFromDisk();
copy(buffer, read, block, needToRead);
}
return buffer;
}
void copy(byte[] dst, int dstFrom, byte[] src, int n) {
for (int s = 0, d=dstFrom; s < n; s++, d++) {
dst[d] = src[s];
}
}
byte[] Read(int sizeInBytes) {
byte[] buffer = new byte[sizeInBytes];
int read = 0, needToRead = sizeInBytes;
byte[] block;
while (needToRead >= 256) {
block = ReadFromDisk();
copy(buffer, read, block, 256);
read += 256;
needToRead -= 256;
}
if (needToRead>0) {
block = ReadFromDisk();
copy(buffer, read, block, needToRead);
}
return buffer;
}
I don't see how is this O(n) time. You call quickSelect k times, Each call is O(j) {j:n..n-k}, so the average time complexity is O(k*n), which is not bad for small k-s, but when k ~ n, then it's close to O(n^2), in which case sorting in O(n*log(n)) might be a better choice.
I might miss something though, maybe because we repeat calling quickSelect on the same array, that get's more and more "sorted" the number of swaps is decreasing in each call, though the number of comparsions don't IMHO.
I also thought about that, but to create the Interval Graph from the input itself is compex, then to find the chromatic number is NP Complete. There are much better solutions above
- titok March 31, 2015