Given a set of intervals, find the interval which has the maximum number of intersections.

Followup to the earlier post, This can be solved in multiple ways.

If the interval is not sparse a good solution might be

public static int getMaxintersection(Interval[] intervals) {

int result = 0;

int[] count;

int min = Integer.MAX_VALUE;

int max = Integer.MAX_VALUE + 1;

// get min and max of the intervals

for (Interval i : intervals) {

if (i.start < min)

min = i.start;

if (i.end > max)

max = i.end;

}

if (min > max)

throw new IllegalArgumentException();

count = new int[max - min + 1];

for (Interval i : intervals)

for (int j = i.start - min; j <= i.end - min; j++)

count[j]++;

for (int i = 0; i < count.length; i++)

if (result < count[i])

result = count[i];

return result;

}

Another approach is sorting the intervals and keeping track of how many intervals have touched the given interval.

`1) Construct two n arrays, one is sort by ai, another is sort by bi.`

make sure that if ai==aj, then bi<bj, but i before j, the same as b-array.

2) Walk through the b-array for each b, Do a binary search in a-array to find

index, make sure a[index]<=b<a[index+1]

3) find the max(index - i + 1), the the bi is the point we need.

public class MergeIntervals {

public class Interval {

public int start;

public int end;

public Interval(int start, int end) {

super();

this.start = start;

this.end = end;

}

}

public class MyComparatorA implements Comparator {

public int compare(Object o1, Object o2) {

Interval i1 = (Interval) o1;

Interval i2 = (Interval) o2;

return i1.start - i2.start;

}

}

public class MyComparatorB implements Comparator {

public int compare(Object o1, Object o2) {

Interval i1 = (Interval) o1;

Interval i2 = (Interval) o2;

return i1.end - i2.end;

}

}

public int getPoint(ArrayList<Interval> intervals) {

// validation

if (intervals == null || intervals.size() == 0) {

return 0;

}

List<Interval> listA = new ArrayList(intervals);

List<Interval> listB = new ArrayList(intervals);

Collections.sort(listA, new MyComparatorA());

Collections.sort(listB, new MyComparatorB());

int max = 0;

int maxPoint = listB.get(0).end;

for (int i = 0; i < listB.size(); i++) {

Interval interval = listB.get(i);

// find B in sortA. ( use binary search)

int index = search(listA, interval.end);

int count = index - i + 1;

if (count > max) {

max = count;

maxPoint = listB.get(i).end;

}

}

return maxPoint;

}

}

## No comments:

Post a Comment