CODEWITHSUNDEEP
algorithm
JTK
JTK

Reputation: 15

What is the best algorithm for putting N points into n intervals

Suppose I have N points in the interval [0,1] and I have already divided this unit interval into n sub-intervals, say [0,x1),[x1,x2),...,[xn-2,xn-1),[xn-1,1] Then I need to determine which sub-interval does each of these N points belong to. What is the best algorithm for completing this job? These sub-intervals do not distribute evenly but they are known. N is O(1 million), n is O(1 k).

Upvotes: 0

Views: 524

Answers (2)

Mukul Varshney
Mukul Varshney

Reputation: 3141

Assuming lower bound of each interval i.e. 0,x1,x2,x3.... are in order, Preserve the 1st value(i.e. lower bounds) of the interval in an array, then use binary search to locate the index greater or less than the number n belongs to.

Upvotes: 1

MBo
MBo

Reputation: 80287

IF points are not sorted, sort them by coordinate.

Do merging (like merge algorithm in MergeSort) for point list with interval list.

Complexity is O(NlogN + N + n) (or O(N + n) if both list are sorted already)

Compare with @Mukul Varshney approach complexity O(Nlogn) and choose the best variant for your case

Upvotes: 1

Related Questions