CareerCup

if the interval is not spare 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.x < min)
min = i.x;
if (i.y > max)
max = i.y;
}

if (min > max)
throw new IllegalArgumentException();

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

for (Interval i : intervals)
for (int j = i.x - min; j <= i.y - min; j++)
count[j]++;

for (int i = 0; i < count.length; i++)
if (result < count[i])
result = count[i];

return result;
}

public static class Interval {
int x;
int y;
}
}}

1. Sort Every points, include start point and end pointer together
2. start from the left start point, increase the value. When we meet a start point, we increase the counter by 1, when we meet a end point, we decrease the counter by 1.
3. The interval which with maximum value in the answer

Complexity O(nlogn) if the interval is bounded

If I name each interval as A, B, C.. and if there are N intervals...
for eg : A = { 7,8,9,10 } B= { 9,10, 11} C = { 1, 2, 3, 4}.........

By intersection, I would get nC2 combinations...
Each combination is of the form .. |A^B|, | A^B|.. etc...

For each interval , sum up the total number of intersection... as below.
|A^B| + | A^B| + | A^C |..... Etc..

The one which has maximum sum is the answer.

This is my understanding.

let intervals be I = [x,y] , sort all the intervals based on their low values . i.e x values .. O(nlgn)

Now , i = 0 ;j = 1 , max = 0 , max_int = a[i] , count = 0 ,start from the first interval interval from the sorted order ...
while ( j < n ) {
while ( a[i] intersect a[j] ) j++ ; count++ ; find the first interval a[j] which doesnot intersect a[i] ....
if count > max then max = count ; max_int = i ; so far i is the interval with most intersections ..

now for( k = 1; (k< j && (a[i+k] doesnot intersect a[j] ;k++ ) ; , find the first interval after i which intersects j ,
count = count - k +1 ;
i = i + k ; //repeat the process with the new index ....
}

total time O(nlgn ) ....

would appreciate if anyone can verify the solution

let intervals be I = [x,y] , sort all the intervals based on their low values . i.e x values .. O(nlgn)

Now , i = 0 ;j = 1 , max = 0 , max_int = a[i] , count = 0 ,start from the first interval interval from the sorted order ...
while ( j < n ) {
while ( a[i] intersect a[j] ) j++ ; count++ ; find the first interval a[j] which doesnot intersect a[i] ....
if count > max then max = count ; max_int = i ; so far i is the interval with most intersections ..

now for( k = 1; (k< j && (a[i+k] doesnot intersect a[j] ;k++ ) ; , find the first interval after i which intersects j ,
count = count - k +1 ;
i = i + k ; //repeat the process with the new index ....
}

total time O(nlgn ) ....

would appreciate if anyone can verify the solution

let intervals be I = [x,y] , sort all the intervals based on their low values . i.e x values .. O(nlgn)

Now , i = 0 ;j = 1 , max = 0 , max_int = a[i] , count = 0 ,start from the first interval interval from the sorted order ...
while ( j < n ) {
while ( a[i] intersect a[j] ) j++ ; count++ ; find the first interval a[j] which doesnot intersect a[i] ....
if count > max then max = count ; max_int = i ; so far i is the interval with most intersections ..

now for( k = 1; (k< j && (a[i+k] doesnot intersect a[j] ;k++ ) ; , find the first interval after i which intersects j ,
count = count - k +1 ;
i = i + k ; //repeat the process with the new index ....
}

total time O(nlgn ) ....

would appreciate if anyone can verify the solution

let intervals be I = [x,y] , sort all the intervals based on their low values . i.e x values .. O(nlgn)

Now , i = 0 ;j = 1 , max = 0 , max_int = a[i] , count = 0 ,start from the first interval interval from the sorted order ...
while ( j < n ) {
while ( a[i] intersect a[j] ) j++ ; count++ ; find the first interval a[j] which doesnot intersect a[i] ....
if count > max then max = count ; max_int = i ; so far i is the interval with most intersections ..

now for( k = 1; (k< j && (a[i+k] doesnot intersect a[j] ;k++ ) ; , find the first interval after i which intersects j ,
count = count - k +1 ;
i = i + k ; //repeat the process with the new index ....
}

total time O(nlgn ) ....

would appreciate if anyone can verify the solution

let intervals be I = [x,y] , sort all the intervals based on their low values . i.e x values .. O(nlgn)

Now , i = 0 ;j = 1 , max = 0 , max_int = a[i] , count = 0 ,start from the first interval interval from the sorted order ...
while ( j < n ) {
while ( a[i] intersect a[j] ) j++ ; count++ ; find the first interval a[j] which doesnot intersect a[i] ....
if count > max then max = count ; max_int = i ; so far i is the interval with most intersections ..

now for( k = 1; (k< j && (a[i+k] doesnot intersect a[j] ;k++ ) ; , find the first interval after i which intersects j ,
count = count - k +1 ;
i = i + k ; //repeat the process with the new index ....
}

total time O(nlgn ) ....

would appreciate if anyone can verify the solution

First, sort the intervals by their starting times. O(nlogn)
Second,
for each interval
use binary search to determine if this interval intersects with others
end for

complexity: #intersections + O(nlogn)

Any better algorithms?

size_t MaxIntersections(std::vector< std::pair<int, int> > intervals)
{
   struct Sorter { 
      bool operator()(const std::pair<int, int>& lhs, const std::pair<int, int>& rhs) {
         return lhs.first < rhs.first;
      } 
   };
   std::sort(intervals.begin(), intervals.end(), Sorter());

   size_t max = 0;
   for (size_t i = 0; i < intervals.size(); ++i)
   {
      int index = intervals.size(), low = 0, high = intervals.size()-1;
      do {
         int mid = (low + high) / 2;
         if (intervals[i].second < intervals[mid].first)
            high = (index = mid) - 1;
         else
            low = mid + 1;
      } while (low <= high);

      if ((index - i) > max)
         max = index - i;
   }
   return max;
}

public class RangesRank {

    private static TreeSet<RangeHolder> sortedRanges;
    private static List<RangeHolder> buffer;

    public static void main(String[] args) {
        sortedRanges = new TreeSet<RangeHolder>();
        sortedRanges.add(new RangeHolder(1.0, 5.0));
        sortedRanges.add(new RangeHolder(2.0, 3.0));
        sortedRanges.add(new RangeHolder(3.5, 4.0));
        sortedRanges.add(new RangeHolder(2.5, 3.75));

        buffer = new LinkedList<RangeHolder>();
        for (RangeHolder range : sortedRanges) {
            checkStack(range);
        }
        RangeHolder range = Collections.max(sortedRanges, new Comparator<RangeHolder>() {
            @Override
            public int compare(RangeHolder rangeHolder, RangeHolder rangeHolder2) {
                return rangeHolder.getRank() - rangeHolder2.getRank();
            }
        });
        System.out.println(range);
    }

    private static void checkStack(RangeHolder holder) {
        Iterator<RangeHolder> iter = buffer.iterator();
        while (iter.hasNext()) {
            RangeHolder range = iter.next();
            if (range.getSecond() < holder.getFirst()) {
                iter.remove();
            }
            else {
                range.increaseRank();
            }
        }
        buffer.add(holder);
    }

    private static class RangeHolder implements Comparable<RangeHolder> {

        private double first;
        private double second;
        private int rank;

        public RangeHolder(double first, double second) {
            this.first = first;
            this.second = second;
            this.rank = 0;
        }

        public double getFirst() {
            return first;
        }

        public double getSecond() {
            return second;
        }

        public void increaseRank() {
            this.rank++;
        }

        public int getRank() {
            return this.rank;
        }

        @Override
        public int compareTo(RangeHolder rangeHolder) {
            if (this.first == rangeHolder.first) {
                if (this.second > rangeHolder.second) {
                    return 1;
                }
                else if (this.second < rangeHolder.second) {
                    return -1;
                }
                return 0;
            }
            return this.first > rangeHolder.first ? 1 : -1;
        }

        @Override
        public String toString() {
            return "RangeHolder{" +
                    "first=" + first +
                    ", second=" + second +
                    ", rank=" + rank +
                    '}';
        }
    }
}

bool comperator(const pair<int,int>& A, const pair<int,int>& B) {
	if(A.first < B.first) return true;
	if(A.first==B.first)
		return A.second>B.second;
	return false;
}

int findMaximumIntersection(vector<pair<int,int>>& pairs) {
	sort(pairs.begin(), pairs.end(), comperator);
	int max_intersection=0;
	for(int i=0; i<pairs.size(); ++i) {
		int lo=0, hi=pairs.size()-1;
		while(lo<hi) {
			int mid=lo+(hi-lo)/2;			
			if(pairs[i].second < pairs[mid].first){
				hi=mid;
			}else{
				lo=mid+1;
			}
		}
		int intersection=(lo-i);	
		max_intersection=max(max_intersection, intersection);
	}
	return max_intersection;
}

I think this is a O(log(2*n)) time complexity algo, where n is a number of Intervals:

define:
class Point {
int x,
boolean isRight;
Interval refToInterval;
}

sort points:
if p1.x == p2.x then p1 < p2 if p2.isRight;
else p1 < p2 if p1.x < p2.x


open_intervals = 0
interval_with_right_most = null

for (point : points _sorted) {
if (point.isRight == false) {
Inteval I = point.intervalRef;
if ( interval_with_right_most == null || I.right > interval_with_right_most.right ) {
interval_with_right_most = I;
}
open++;
ans = Math.max(ans, open);
else {
open --;
}
}
ans = Math.max(ans, open);