CODEWITHSUNDEEP
algorithmlanguage-agnostic
Ram Swami
Ram Swami

Reputation: 371

Interview - Sorting based on start and end value

I got this question in one of my interview. There was an array of objects which was associated with start value and end value. The count associated with each object is the number of other objects with greater start time and lesser end time. So I had to find the count associated with each object.

I came up with O(n^2) solution, where first I sorted on start value and then checked each object's end value with the end values of next objects to get count. Can there be better algorithm to tackle this problem.

Upvotes: 1

Views: 135

Answers (1)

throwit
throwit

Reputation: 714

I did't find a simple way to solve it, maybe a little complex.

I came up with an O(nlogn) solution. Like your solution, first I sort on start value but in descending order. Then applying for a new array a[] keeping the occurrence number of end value (That is, when meeting an object (start, end), make a[end] plus one). Then traverse the object array, for object i with (start, end), we just need add sum(a[i] | 0<=i<=end) to final answer, then update array a with a[end] ++, for the sum() query, we can use Fenwick tree or Segment tree to calculate every query in O(logn), so the total complexity is O(nlogn).

Upvotes: 3

Related Questions