Monday, March 19, 2012

Key search in n non overlapping intervals.


Given n non overlapping intervals and an element. Find the interval into which this element falls.


Approach:
Sort the intervals according to start time.
Do a binary search for the key among the intervals.


Code input/output:
7 - number of intervals
2 5
6 9
17 21
23 29
31 39
40 43
47 50


printing intervals: 
2-5
6-9
17-21
23-29
31-39
40-43
47-50


Search key 48 found in the following interval
47-50
Search key 22 not found in any of interval!

No comments:

Post a Comment