Merge sort – Let us code

Counting the number of inversions in a list

August 20, 2014October 26, 2020adminLeave a comment

Given an array of numbers, how do we count the number of inversions in it? Suppose we are sorting an array of numbers in increasing order, an inversion is an ordered pair of indices (i,j) such that i < j and A[i] > A[j] . For example consider the array {3, 2, 1,…

Maximum number of overlapping intervals

August 8, 2014adminLeave a comment

Given a set of intervals, how do we find the maximum number of intervals overlapping at any point of time. For example let us consider the following intervals. { (0,2), (3, 7), (4,6), (7,8), (1,5) } The maximum number of intervals overlapped is 3 during (4,5). This can be asked in many forms in a…