CareerCup

I don't think this question can be solved in O(N+K). The best I can think of is O(N log K) or O(K log N), depending on which one is larger.

I have simple solution of bucket filling where we take array of size k+1. For interval I[si, ei], we do following:

for (int i = si; i <= ei; i++)
	arr[i]++;

But this solution takes O(nk). Please let me know if O(n + k) algorithm is found.

Here seems to be a Theta(n+k) solution.

/* 
Note that to way to do it most optimally is
to generate a indices map from the ranges, 
which does not require a sorting.
Once the dictionary is created, 
all we do is traverse over the indices range given 
[0,k] ; or in ZoomBA [0:k+1] -> and print counts
or zero if the index is not found.
*/
range = [ [5,7],[1,4],[2,3],[6,8],[3,5] ] 
// this takes ( min to max )
d = fold( range , dict() ) -> {
   #(b,e) = $.o // items are tuples
   for ( i : [b:e+1] ){
    // add indices and store counts 
    if ( i @ $.p ){
      $.p[i] += 1
    }else{
      $.p[i] = 1
    }
  }
  $.p
}
println ( d )
// produce the result 
ar = [0:9] // from 0 to 8 indices 
fold ( ar ) -> {  printf ( '%d -> %d\n', $.o , $.o @ d ? d[$.o] : 0 )  }

public class P5709181349789696 implements IProgram {
    @Override
    public void run(String[] args) throws Exception {
        Range[] ranges = {new Range(5, 7), new Range(1, 4), new Range(2, 3), new Range(6, 8), new Range(3, 5)};
        int k = 8;
        int[] result = solve(ranges, k);

        for (int i = 0; i < result.length; i++) {
            System.out.println(result[i]);
        }
    }

    private int[] solve(Range[] ranges, int k) {
        int[] starts = new int[k + 1];
        int[] ends = new int[k + 1];

        // O(n)
        for (Range range : ranges) {
            starts[range.start] += 1;
            ends[range.end] += 1;
        }

        int[] result = new int[k + 1];

        int tmp = 0;
        // O(k)
        for (int i = 0; i <= k; i++) {
            tmp += starts[i];
            result[i] = tmp;
            tmp -= ends[i];
        }

        return result;
    }

    private static class Range {
        final int start;
        final int end;

        private Range(int start, int end) {
            this.start = start;
            this.end = end;
        }
    }
}