CareerCup

Assumptions:
1. The times are not hours, but some measure. could be day, could be millis, etc
2. The flow rates are always positive

Simple algorithm that will running in O(n log n):
1. Sort all the events by their start time into a priority queue (earliest First) (heap1)
2. create a Priority Queue of events sorted by their end time (earliest first) (heap2)
4. create a value to track the best flow rate total
5. create a value to track the running flow rate total
6. while contents still exist in the heap1
___a. find the earliest value from heap1 and heap2
___b. while heap1 starts with the earliest starting time
______i. remove the event from heap1 with that starting time.
______ii. add the flow rate from the event to the running value total
______iii. add the event to heap2
___c. while heap2 starts with the earliest ending time
______i. remove the event from heap2 with that ending time
______ii. remove the flow rate from the even from the running total
___d. if the running flow rate total is better than the best flow rate total, store it
7. return the best flow rate total

static class Event{
	int startTime, endTime, rate;
}

public static int getMaxFlow(Event[] events){
	PriorityQueue<Event> heap1 = new PriorityQueue<Event>(events.length, new Comparator<Event>(){
		public int compare(Event e1, Event e2){
			return e2.startTime-e1.startTime;
		}
	});
	PriorityQueue<Event> heap2 = new PriorityQueue<Event>(events.length, new Comparator<Event>(){
		public int compare(Event e1, Event e2){
			return e2.endTime-e1.endTime;
		}
	});
	for(Event event : events){
		heap1.add(event);
	}
	int bestFlowRate = Integer.MIN_VALUE;
	int totalFlowRate = 0;
	while(!heap1.isEmpty()){
		int earliest = heap1.peak().startTime;
		if(!heap2.isEmpty() && heap2.peek().endTime < earliest){
			earliest = heap2.peek().endTime;
		}
		while(!heap1.isEmpty() && heap1.peek().startTime == earliest){
			Event event = heap1.poll();
			totalFlowRate += event.rate;
			heap2.add(event);
		}
		while(!heap2.isEmpty() && heap2.peek().endTime == earliest){
			Event event = heap2.poll();
			totalFlowRate -= event.rate;
		}
		if(totalFlowRate > bestFlowRate){
			bestFlowRate = totalFlowRate;
		}
	}
	return bestFlowRate;
}

Edit: PriorityQueue constructor using a comparator must also have a capacity specified...

private static void maxFlowInAInstance() {

		class Flow{
			private int start; 
			private int end;
			private int flow;
			Flow(int start,int end, int flow){
				this.start=start;
				this.end=end;
				this.flow=flow;
			}
			
			public int getStart() {
				return start;
			}

			public int getEnd() {
				return end;
			}
			
			public int getFlow() {
				return flow;
			}
			
		}
		
		Flow[] flows = { new Flow(0,10,100), new Flow(10,15,300), new Flow(16,20,400), new Flow(5,15,200)};
		int maxFlow=0;
		int instance=0;
	    Map<Integer,Integer> map = new HashMap<Integer,Integer>();
		for(Flow flow : flows){
			for(int start=flow.getStart();start<flow.getEnd();start++ ){
				Integer abc = map.containsKey(Integer.valueOf(start)) ?						
						map.put(start, map.get(start)+flow.getFlow()):map.put(start, flow.getFlow());
						if(map.get(start) > maxFlow){
							
							maxFlow=map.get(start);
							instance=start;
						}
			}
		}
		System.out.println("************* Max Flow : "+ maxFlow +"  , instance:"+instance);
	}

Why not only use one PriorityQueue and push both start and endtimes on it?
Endtimes are sorted behind starttimes and have negative values (as the value that was pushed with starttime must be removed again.

Here is some code (untested)

class Entry implements Comparable {
	final int value;
	final long timestamp;
	final boolean isStartEvent;

	public Entry(int value, long timestamp, boolean isStartEvent) {
		this.value = value;
		this.timestamp = timestamp;
		this.isStartEvent= isStartEvent;
	}
	
	@Override
	public int compareTo(Entry e) {
		if(timstampe != e.timestamp) return timestamp - e.timestamp;
		return isStartEvent ? -1 : 1; // start events must be smaller then end events
	}
}

// given
class Flow {
	long start;
	long end;
	int value;
}

public static int maxFlow(List<Flow> flows) {
	PriorityQueue<Entry> queue = new PriorityQueue<>();

	// push all start and end times on queue
	for(Flow f : flows) {
		queue.add(new Entry( f.value, f.start, true);
		queue.add(new Entry( -f.value, f.end, false);
	}

	int maxSum = 0;
	int curSum = 0;
	// process queue
	while( !queue.isEmpty()) {
		Entry e = queue.poll();
		curSum = curSum + e.value;
		maxSum = Math.max(maxSum, curSum);	
	}
	return maxSum;
}

I would create an array of size 24 to represent the hours of the day;
then for each interval I would add the flow of the interval at the start hour of that interval in the array and subtract the flow of that interval at the end+1 hours of that interval.

After I have populated the array in this way I will find the maxFlow in the array just by scanning the array and keeping the running sum. The max value of the running sum is the MaxFlow.
O(n) time complexity, O(1) space complexity. We could use a sorted Collection to avoid all the empty values in the array but in this case we will lose time to keep the keys sorted, an insertion will take O(logn) and the final time complexity would be O(nlogn). As we are computing intervals just for 24 hours we can assume the cost of having some non used slots in an array of size 24.

Example:

0,10,100 
10,15,300 
16,20,400 
5,15,200

the array would be populated with the following values:

[0]-> 100
[1]-> 0
[2]-> 0
[3]-> 0
[4]-> 0
[5]-> 200
[6]-> 0
[7]-> 0
[8]-> 0
[9]-> 0
[10]-> 300
[11]->-100
[12]-> 0
[13]-> 0
[14]-> 0
[15]-> 0
[16]->-100
[17]-> 0
[18]-> 0
[19]-> 0
[20]-> 0
[21]->-400
[22]-> 0
[23]-> 0

and the running sum will be:

100,100,100,100,100,300,300,300,300,300,600,500,500,500,500,500,400,400,400,400,400,0,0,0

just keep the max while computing the running sum.

This is the code for this solution:

import java.util.*;

class FlowInterval {
	int start;
	int end;
	int flow;
	public FlowInterval(int start, int end, int flow) {
		this.start=start;
		this.end=end;
		this.flow=flow;
	}
	public String toString() {
		return "("+this.start+","+this.end+"):"+this.flow;
	}
}
public class MaxFlow {
	public static int maxFlow(List<FlowInterval> intervals) {
		int maxFlow = 0;
		int currentFlow = 0;
		int[] hours = new int[24];
		for(FlowInterval flowint: intervals) {
			hours[flowint.start]+=flowint.flow;
			hours[flowint.end+1]-=flowint.flow;
		}
		for(int i=0;i<hours.length;i++) {
			currentFlow = currentFlow+hours[i];
			if(currentFlow>maxFlow) {
				//System.out.println("Found new MaxFlow of "+currentFlow+" at "+String.format("%02d", i)+":00");
				maxFlow=currentFlow;
			}
		}
		return maxFlow;
	}
	public static void main(String[] args) {
		FlowInterval f1 = new FlowInterval(0,10,100);
		FlowInterval f2 = new FlowInterval(10,15,300);
		FlowInterval f3 = new FlowInterval(16,20,400);
		FlowInterval f4 = new FlowInterval(5,15,200);
		List<FlowInterval> intervals = new ArrayList<FlowInterval>();
		intervals.add(f1);
		intervals.add(f2);
		intervals.add(f3);
		intervals.add(f4);
		System.out.println(intervals);
		System.out.println("MaxFlow: "+maxFlow(intervals));
	}
}

Here is very primitive code for this problem-
idea is-
1. array[24]
2. for each range add up the flow
3. get the max out of the array.


int H[24]={0};

int main()
{
int min, max, value, cmax=0, i, moment;
while(scanf("%d %d %d", &min, &max, &value) != EOF)
{
for(i=min; i<=max; i++)
H[i]+=value;
}
for(i=0; i<24; i++)
{
if( cmax < H[i])
{
cmax = H[i];
moment= i;
}
}

printf("\nmax flow is at moment %d, and vlaue is %d\n", moment, cmax);

return 0;
}

#include<stdio.h>
#include<stdlib.h>


int day[24] = {0};

main()
{
int start,end,amount,i,max=0,instinct;;
printf("enter the start,end and amount\n");
while(scanf("%d%*c%d%*c%d",&start,&end,&amount) != EOF)
{
        for(i= start;i<=end;i++)
        {
                day[i]+= amount;
        }
}

for(i=0;i<24;i++)
{
        if(day[i]>max)
        {
                max = day[i];
                instinct = i;
        }
}

printf("instinct %i max %i",instinct,max);
}

0. Store all the intervals as a list of 2 element arrays. Call this list "intervals". It would look something like {[0,10],[10,15],[16,20],[5,15]}. Also create a list called "flows", {100,300,400,200}.
1. Store all the start and end times in a list. Sort the list and remove duplicate elements from it. Call this list "times", {0,5,10,15,16,20}.
2. Create a zero initialized list of integers of the same size as "times". The flow rates for all these "times" will be stored in the corresponding elements of this list. Call this list "new_flows".
3. Iterate through all the elements of "times". For every element of "times", iterate through all the elements of "intervals" and check if the time lies in this particular interval. If it does, increment the corresponding element of "new_flows" by the corresponding value in "flows".
4. Find the maximum value in the array "new_flows".

Here is a C++ implementation of the above algorithm

#include <iostream>
using namespace std;
#include <list>
#include <stdio.h>
#include <fstream>
#include <string>
#include <vector>


int main(int argc, const char * argv[])
{

    list<int> start,end,flow;
    string line;
    string filename = "file.txt";
    fstream myfile(filename);
    if(myfile.is_open())
    {
        while(true)
        {
            int s,e,f;
            char c = ',';
            myfile>>s>>c>>e>>c>>f;
            start.push_back(s);
            end.push_back(e);
            flow.push_back(f);
            if(!getline(myfile,line))
            {
                break;
            }
        }
        myfile.close();
    }
    else{
        cout<<"Could not open file\n"<<endl;
    }
    list<int> times;
    list<int>::iterator i;
    cout<<"Start"<<endl;
    for(i = start.begin();i!=start.end();i++)
    {
        times.push_back(*i);
        cout<<*i<<"\t";
    }
    cout<<endl;
    cout<<"End"<<endl;
    for(i = end.begin();i!=end.end();i++)
    {
        times.push_back(*i);
        cout<<*i<<"\t";
    }
    cout<<endl;
    cout<<"Flow"<<endl;
    for(i = flow.begin();i!=flow.end();i++)
    {
        cout<<*i<<"\t";
    }
    
    times.sort();
    times.unique();
    cout<<endl;
    cout<<"Times"<<endl;
    for(i = times.begin();i!=times.end();i++)
    {
        cout<<*i<<"\t";
    }
    cout<<endl;
    int num_intervals = start.size();
    int size = times.size();
    vector<int> new_flow(size);
    int j;
    for(j=0;j<size;j++)
    {
        new_flow[j]=0;
    }
    vector<int> intervals(2*num_intervals);
    list<int>::iterator x;
    list<int>::iterator y;
    x = start.begin();
    y = end.begin();
    j = 0;
    while(x!=start.end())
    {
        intervals[j] = *x;
        intervals[j+1] = *y;
        x++;
        y++;
        j = j+2;
    }
    
    j = 0;
    for(x = times.begin();x!=times.end();x++)
    {
        y = flow.begin();
        for(int k=0;k<2*num_intervals;k+=2)
        {
            
            if(*x<intervals[k] || *x>intervals[k+1])
            {
                
            }
            else
            {
                new_flow[j] = new_flow[j]+(*y);
            }
            y++;
        }
        j++;
    }
    cout<<endl;
    cout<<"New flows"<<endl;
    int max = 0;
    for(j=0;j<size;j++)
    {
        cout<<new_flow[j]<<"\t";
        if(new_flow[j]>max)
        {
            max = new_flow[j];
        }
    }
    cout<<endl;
    cout<<"The maximum flow is "<<max<<endl;
    
    
    return 0;
    
    
    
    
}

R

a <- matrix(c(0,10,100,10,15,300,16,20,400,5,15,200), ncol=3, byrow=T)
> a
[,1] [,2] [,3]
[1,]    0   10  100
[2,]   10   15  300
[3,]   16   20  400
[4,]    5   15  200


alla <- data.frame()
for(i in 1:nrow(a)){
  sa <- seq(a[i,1], a[i,2], by = 1)
  ta <- data.frame(sa, rep(a[i,3], length(sa) ))
  alla <- rbind(alla, ta)
}
names(alla) <- c('time', 'flow')

ag <- aggregate(alla$flow, by=list(alla$time), FUN=sum)
ag[which.max(ag[,2]),]

Written in C++ using heap data structure.

struct Entry{
    int start;
    int end;
    int flow;
};

struct CompStart
{
    bool operator()(const Entry& a, const Entry& b)
    {
        return a.start > b.start;
    }
};

struct CompEnd
{
    bool operator()(const Entry& a, const Entry& b)
    {
        return a.end > b.end;
    }
};

int findMaxFlow(vector<Entry> entries)
{
    vector<Entry> entriesStart(entries);
    vector<Entry> entriesEnd(entries);

    make_heap(entriesStart.begin(), entriesStart.end(), CompStart());
    make_heap(entriesEnd.begin(), entriesEnd.end(), CompEnd());

    int runningFlow = 0;
    int maxFlow = 0;
    int time = 0;
    while(!entriesStart.empty())
    {
        time = entriesStart.front().start;
        runningFlow += entriesStart.front().flow;

        pop_heap(entriesStart.begin(), entriesStart.end(), CompStart());
        entriesStart.pop_back();
        make_heap(entriesStart.begin(), entriesStart.end(), CompStart());

        while(!entriesEnd.empty() && time >= entriesEnd.front().end)
        {
            time = entriesEnd.front().end;
            runningFlow -= entriesEnd.front().flow;

            pop_heap(entriesEnd.begin(), entriesEnd.end(), CompEnd());
            entriesEnd.pop_back();
            make_heap(entriesEnd.begin(), entriesEnd.end(), CompEnd());

            if(runningFlow > maxFlow)
                maxFlow = runningFlow;
        }

        if(runningFlow > maxFlow)
            maxFlow = runningFlow;
    }

    return maxFlow;
}

int main()
{
    vector< Entry > entries = {{0,10,100}, {10,15,300}, {16,20,400}, {5,15,200}};

    cout << findMaxFlow(entries) ;

    return 0;
}