CareerCup

Sort start times with an nlogn sorting algorithm and store it.
Sort end times with an nlogn sorting algorithm and store it.

We traverse sorted start times and add to an accumulator, but after traversing one start time, we traverse as many end times as needed to "catch up" to the start time and we subtract that from the accumulator. Take the max of accumulator vs the current max at each traversal.

O(nlogn)

Here's my O(nlogn) solution.Basically it's the same as what @zd said.

More explanations:
Think of time intervals as a bunch of segments (with start and end points). Now we want to find a point which has most weighted(memory usage) intersection with other segments.

For sure the answer is one of the start points.
We can add all start and end points to a vector (with their type(start or end) and their original index in segments) and sort them.
Now we start from left to right, and keep track of sum of all memory usages which are currently having intersection with each other.At each end point we just need to subtract the memory usage of that segment, and at each start point just add the new memory usage and see whether we have a maximum answer so far.

The tricky point is that in case of equal dates(times), start points should be on the left of end points.

Here's the my implementation in C++.

int findBusyHour(vector< pair<pair<int,int>,int > > times)
{
	int N=times.size();

	vector< pair<int, pair<int,int> > > points; // (time,(isEndPoint,OriginalIndex))
	for (int i=0;i<N;i++){
		points.push_back({times[i].first.first,{0,i}});
		points.push_back({times[i].first.second,{1,i}});
	}

	sort(points.begin(),points.end());

	int cur=0,maxi=0;
	int ans=0;
	for (int i=0;i<2*N;i++){
		int ind=points[i].second.second;
		int isEnd = points[i].second.first;
		int h=points[i].first;
		if (isEnd){//end point
			cur-=times[ind].second;
		}
		else{
			cur+=times[ind].second;
			if (cur>maxi){
				maxi = cur;
				ans = h;
			}
		}

	}

	return ans;
}

Split log to 2 nodes, start and end. Start node has positive memory and end node has negative memory. Sort all nodes, and process each nodes.

Example)
100207 100208 2
100305 100307 5
100207 100209 4

split ==>

100207 2
100208 -2
100305 5
100307 -5
100207 4
100209 -4

sort ==>

100207 2
100207 4
100208 -2
100209 -4
100305 5
100307 -5

#include <iostream>
#include <map>

using namespace std;

int findBusyHour(int log[][3], int n) {
	multimap<int, int> nodes;
	multimap<int, int>::iterator it;
	int i, maxHour, maxMemory, hour, memory, released;

	i = 0;
	while (i < n) {
		nodes.insert(make_pair(log[i][0], log[i][2]));
		nodes.insert(make_pair(log[i][1], -log[i][2]));
		i++;
	}

	maxHour = -1;
	maxMemory = 0;
	hour = -1;
	memory = 0;
	released = 0;

	it = nodes.begin();
	while (it != nodes.end()) {
		if (hour != it->first) {
			hour = it->first;
			memory += released;
			released = 0;
		}
		if (it->second > 0) {
			memory += it->second;
			if (memory > maxMemory) {
				maxHour = hour;
				maxMemory = memory;
			}
		} else {
			released += it->second;
		}
		it++;
	}

	return maxHour;
}

int main(int argc, char* argv[]) {
	int log[][3] = {
		{100207, 100208, 2},
		{100305, 100307, 5},
		{100207, 100209, 4},
		{111515, 121212, 1}
	};

	cout << findBusyHour(log, 4) << "\n";

	return 0;
}

It is a classic problem, we can use a cumulative array

static const int MAX = 111225;

int findHeighestMemoryUsageHour() {
	int usagePerHour[MAX] = {0};
	int start, end, usage;
	while (cin >> start >> end >> usage) {
		start -= 10000;
		end -= 10000;
		usagePerHour[start] += usage;
		usagePerHour[end + 1] -= usage;
	}

	for (int i = 1; i < MAX; ++i)
		usagePerHour[i] += usagePerHour[i - 1];

	int res = 0, maxUsage = 0;
	for (int i = 0; i < MAX - 1; ++i) {
		if (usagePerHour[i] > maxUsage) {
			res = i;
			maxUsage = usagePerHour[i];
		}
	}

	return res + 10000;
}

Isnt it the classic problem of finding continuous max sum?

if we simplify this problem then it would look like following:
((startTime,endTime),val):
((1,2),2) ((3,4),5) ((1,3),4) ((5,6),1)
now we sort the start time and then we merge intervals along with the values. As we are merging we also keep track of the max value and in the end we return the interval with max value.

Sorting takes O(nlogn) + merging takes O(n), so running time is O(nlogn)

Is this a possible solution that doesn't involve sorting?

Since time is MMDDHH, the maximum integer is 123124 or 130000 to be safe. Maybe we can create an array, int[130000], where each element represents the memory usage. The index represents the "time". As we process each log entry, we can fill in the array. For instance, processing

100305 100307 5

means adding 5 to the array at each index 100305 to 100307. Then afterwards, we run a for loop to determine the maximum memory usage.

Actually I think this is similar to what malinbupt implemented? I only know c# so I'm not
exactly sure what's going on.

Worst case time complexity => O(n)
Worst case space complexity (excluding the input itself) => O(1)

MMDDHH time format indicates that that input space ranges from 010101 to 123124 which is 8928 values.

With this observation in mind, we can create two hash maps (you can use arrays if you like). For each start time, update the value to 'value in the hash map + value (memory occupied) of the current start time'. Lets call this map as mapA.

Do the same for end times in a separate hash map. Lets call this map as mapB.

Now maintain an List bound by size 4 'maxStartTimeList'. A value for maximun size seen so far. Lets call it 'maxSize'. Also, the current size 'currSize'

Iterate over mapA. for each key in mapA and corresponding key in mapB get their values. v1 and v2.

Then for each key,

currSize = currSize + v1 - v2
if(currSize == maxSize) {
    maxStartTimeList.add(currStartTime);
    if(maxStartTimeList.size() == 4) {
        return maxStartTimeList;
    }
} else if(currSize > maxSize) {
    replace the list with a new one and add the startTime to that list
} else just move on.

Note that you don't need mapA and mapB in order of 'startTime' or 'endTime'

(Please correct me if I am wrong :-P. Working on the code next.)

Worst case time complexity => O(n)
Worst case space complexity => O(1)

MMDDHH time format indicates that that input space ranges from 010101 to 123124 which is 8928 values.

With this observation in mind, we can create two hash maps (you can use arrays if you like). For each start time, update the value to 'value in the hash map + value (memory occupied) of the current start time'. Lets call this map as mapA.

Do the same for end times in a separate hash map. Lets call this map as mapB.

Now maintain an List bound by size 4 'maxStartTimeList'. A value for maximun size seen so far. Lets call it 'maxSize'. Also, the current size 'currSize'

Iterate over mapA. for each key in mapA and corresponding key in mapB get their values. v1 and v2.

Then for each key,

currSize = currSize + v1 - v2
if(currSize == maxSize) {
    maxStartTimeList.add(currStartTime);
    if(maxStartTimeList.size() == 4) {
        return maxStartTimeList;
    }
} else if(currSize > maxSize) {
    replace the list with a new one and add the startTime to that list
} else just move on.

(Please correct me if I am wrong :-P )

Note that you don't need mapA and mapB in order of 'startTime' or 'endTime'

How can my solution be improved?

#input:100207 100208 2
			#October 02 7am -> 8am  (memory:2)
			#100305 100307 5
			#111515 121212 1
			#max is 123124


#if two intervals intersect, do a union
#otherwise, add the interval 

def busiestHour(timeList):
	start = [int(x) for x in timeList[::3]]
	end = [int(x) for x in timeList[1::3]]
	memory = [int(x) for x in timeList[2::3]]
	zipped = zip(start,end,memory)
	abc = [0]*123125
	for i in zipped:
		for j in range(int(i[0]),int(i[1])+1):
			abc[j] = abc[j] + i[2]

	hour = max(abc)
	return abc.index(max(abc)))		
	

log = "100207 100208 2\n100305 100307 5\n100207 100209 4\n111515 121212 1"
timeSet = log.split()

print(busiestHour(timeSet))

I couldn't understand the problem, why the answer to given input is 100207 ? Please explain if someone read this.

Most of the solution I am seeing assumes that we have memory large enough to store all the logs in memory for sorting. How would solution change if I cannot bring all the nodes in memory for sorting??? Just curious!!!!!

public int getHourMax(String[] logs)
{
	int[] usageData=new int[123100-10100+1];///123100 represents 12/31 at hour 00 10100 represents 01/01/ hour 00
	int maxUsage=Integer.MIN_VALUE();
	int maxUsageHour=0;
	for(String s:logs)
	{
		int[] arr=s.split();//Split the log entry into three elements (start date and time, end date and time, usage)
		//get start 
		int start=Integer.parseInt(arr[0]).intValue();
		//get end 
		int end=Integer.parseInt(arr[1]).intValue();
		//get usage
		int usage=Integer.parseInt(arr[2]).intValue();
		
		//find the indices in the array corresponding to start and end. Add usage to each of the values in these positions. Keep track of the maximum 
		//usage amount encountered at each update to the array
		int i=start-10100;
		int j=end-10100;
		 while(i<=j)
		 {
			usageData[i] += usage;
			if(usageData[i]>maxUsage)
			{
					maxUsage=usageData[i];
					maxUsageHour=i+10100;
			}
		 }
	}
	return maxUsageHour;
}

//Worst time complexity O(n). Space complexity is O(1)

I really like Malinbupt's approach. Here it is in Java:

public class Log {
	
	private static final int MAX = 123124;
	
	private int start;
	private int end;
	private int usage;
		
	public Log(int start, int end, int usage) {
		this.start = start;
		this.end = end;
		this.usage = usage;
	}
	
	public static int findPeak(Log... logs) {
		int [] usageArray = new int[MAX + 2];
		for (int i = 0; i < logs.length; ++i) {
			usageArray[logs[i].start] += logs[i].usage;
			usageArray[logs[i].end + 1] -= logs[i].usage;
		}
		
		int maxSoFar = usageArray[0];
		int time = 0;
		for (int i = 1; i <= MAX; ++i) {
			usageArray[i] += usageArray[i - 1];
			if (usageArray[i] > maxSoFar) {
				maxSoFar = usageArray[i];
				time = i;
			}
		}
		
		return time;
	}

}

O(N) time, O(N) space

import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;


class Log{
	
	
	public Log(int startTime, int endTime, int cpu) {
		super();
		this.startTime = startTime;
		this.endTime = endTime;
		this.cpu = cpu;
	}
	int startTime;
	int endTime;
	int cpu;
}

public class CpuHighest {


	public static void main(String[] args){
		List<Log> logs = new LinkedList<Log>();
		logs.add(new Log(100207,100208,2));
		logs.add(new Log(100305,100307,5));
		logs.add(new Log(100207,100209,4));
		logs.add(new Log(111515,121212,1));
		Hashtable<Integer,Integer> hourlyCpuMap = new Hashtable<Integer,Integer>();
		int max=0;
		int time=0;
		for(Log l : logs){
			int tDiff = l.endTime - l.startTime;
			int avgCpu = l.cpu / tDiff;
			for(int i=l.startTime; i<=l.endTime; i++){
				Integer hourlyCpu = hourlyCpuMap.get(i);
				if(hourlyCpu!= null)
					hourlyCpuMap.put(i, hourlyCpu+avgCpu);
				else
					hourlyCpuMap.put(i,avgCpu);
				if(hourlyCpu != null && hourlyCpu > max){
					max = hourlyCpu;
					time = i;
				}
			}
			
		}
		
		System.out.println(time);

	}

}

import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;


class Log{
	
	
	public Log(int startTime, int endTime, int cpu) {
		super();
		this.startTime = startTime;
		this.endTime = endTime;
		this.cpu = cpu;
	}
	int startTime;
	int endTime;
	int cpu;
}

public class CpuHighest {


	public static void main(String[] args){
		List<Log> logs = new LinkedList<Log>();
		logs.add(new Log(100207,100208,2));
		logs.add(new Log(100305,100307,5));
		logs.add(new Log(100207,100209,4));
		logs.add(new Log(111515,121212,1));
		Hashtable<Integer,Integer> hourlyCpuMap = new Hashtable<Integer,Integer>();
		int max=0;
		int time=0;
		for(Log l : logs){
			int tDiff = l.endTime - l.startTime;
			int avgCpu = l.cpu / tDiff;
			for(int i=l.startTime; i<=l.endTime; i++){
				Integer hourlyCpu = hourlyCpuMap.get(i);
				if(hourlyCpu!= null)
					hourlyCpuMap.put(i, hourlyCpu+avgCpu);
				else
					hourlyCpuMap.put(i,avgCpu);
				if(hourlyCpu != null && hourlyCpu > max){
					max = hourlyCpu;
					time = i;
				}
			}
			
		}
		
		System.out.println(time);

	}

}

import java.util.Hashtable;
import java.util.LinkedList;
import java.util.List;


class Log{


public Log(int startTime, int endTime, int cpu) {
super();
this.startTime = startTime;
this.endTime = endTime;
this.cpu = cpu;
}
int startTime;
int endTime;
int cpu;
}

public class CpuHighest {


public static void main(String[] args){
List<Log> logs = new LinkedList<Log>();
logs.add(new Log(100207,100208,2));
logs.add(new Log(100305,100307,5));
logs.add(new Log(100207,100209,4));
logs.add(new Log(111515,121212,1));
Hashtable<Integer,Integer> hourlyCpuMap = new Hashtable<Integer,Integer>();
int max=0;
int time=0;
for(Log l : logs){
int tDiff = l.endTime - l.startTime;
int avgCpu = l.cpu / tDiff;
for(int i=l.startTime; i<=l.endTime; i++){
Integer hourlyCpu = hourlyCpuMap.get(i);
if(hourlyCpu!= null)
hourlyCpuMap.put(i, hourlyCpu+avgCpu);
else
hourlyCpuMap.put(i,avgCpu);
if(hourlyCpu != null && hourlyCpu > max){
max = hourlyCpu;
time = i;
}
}

}

System.out.println(time);

}

}

public class GoogleLogs {

    private static int[] durationLogs;
    public static final int MAX = 123123;
    public static final int MIN = 10100;

    public static void main(String[] args) throws IOException {

        durationLogs = new int[MAX - MIN + 1];
        String dirPath = args[0];
        String fileName = args[1];
        // run loop in case of multiple files
        readFile(dirPath, fileName);
        int maxUsage = Integer.MIN_VALUE, duration = 0;
        for (int i = 1; i < MAX - MIN; ++i) {
            durationLogs[i] += durationLogs[i - 1];
            if (durationLogs[i] > maxUsage) {
                maxUsage = durationLogs[i];
                duration = i + MIN;
            }
        }

        System.out.printf("Max Usage %d is at time %d", maxUsage, duration);
    }

    private static void readFile(String dir, String fileName) throws IOException {
        Path path = Paths.get(dir, fileName);
        try (Stream<String> lines = Files.lines(path)) {
            lines.forEach(line -> {
                String[] words = line.split(" ");
                int start = Integer.parseInt(words[0]);
                int end = Integer.parseInt(words[1]);
                int usage = Integer.parseInt(words[2]);
                durationLogs[start - MIN] += usage;
            });
        }
    }
}

Here is a working solution in O(n * logn) time, and O(n) space.
The idea is to have one array sorted by start time and another one by end time. This allows us to track currently "open" logs.

We go through logs and increase the current memory usage when some interval is opening and decrease memory usage when some interval is closing:

public class MaximumMemoryUsageInLogs {

    public static void main(String[] args) {
        LogRecord[] logs = new LogRecord[]{new LogRecord("100207", "100209", 4), new LogRecord("100305", "100307", 5),
                new LogRecord("100207", "100208", 2), new LogRecord("111515", "121212", 1)};

        System.out.println(computeMaximumUsage(logs));

        logs = new LogRecord[]{new LogRecord("100207", "100211", 2), new LogRecord("100209", "100215", 5),
                new LogRecord("100214", "100218", 3), new LogRecord("100211", "100213", 6),
                new LogRecord("100208", "100209", 4)};

        System.out.println(computeMaximumUsage(logs));
    }

    private static String computeMaximumUsage(LogRecord[] logs) {
        LogRecord[] byStart = Arrays.copyOf(logs, logs.length);
        Arrays.sort(byStart, LogRecord.BY_START);

        LogRecord[] byEnd = Arrays.copyOf(logs, logs.length);
        Arrays.sort(byEnd, LogRecord.BY_END);

        int currentUsage = 0, maxUsage = 0;
        String maxTime = "";
        int i = 0, j = 0;

        while (i < byStart.length) {
            if (byStart[i].start.compareTo(byEnd[j].end) > 0) {
                currentUsage -= byEnd[j].usage;
                j++;
            } else {
                currentUsage += byStart[i].usage;
                if (currentUsage > maxUsage) {
                    maxUsage = currentUsage;
                    maxTime = byStart[i].start;
                }

                i++;
            }
        }

        return maxTime;
    }


    private static class LogRecord {
        private String start;
        private String end;
        private int usage;

        private static Comparator<LogRecord> BY_START = Comparator.comparing(l -> l.start);
        private static Comparator<LogRecord> BY_END = Comparator.comparing(l -> l.end);

        public LogRecord(String start, String end, int usage) {
            this.start = start;
            this.end = end;
            this.usage = usage;
        }

        @Override
        public String toString() {
            return "LogRecord{" +
                    "start='" + start + '\'' +
                    ", end='" + end + '\'' +
                    ", usage=" + usage +
                    '}';
        }
    }
}

public class LogMemory {
	
	public int calcMaxMemoryUsage(List<Log> ip){
		if(ip==null || ip.size()==0)
			return 0;
		if(ip.size() == 1)
			return ip.get(0).u;
		Collections.sort(ip, new Comparator<Log>(){
			public int compare(Log l1,Log l2){
				return l1.s-l2.s;
			}
		});
		
		Map<Integer,ArrayList<Integer>> map = new HashMap<>();
		ArrayList<Integer> temp = new ArrayList<Integer>();
		temp.add(ip.get(0).u);
		map.put(ip.get(0).e,temp);
		int curUsage = ip.get(0).u; int maxUsage = 0;
		for(int i=1;i<ip.size();i++){
			Log cur = ip.get(i);
			curUsage += cur.u;
			List<ArrayList<Integer>> less = getEndTimeLessThanCur(cur.s,map);
			for(List<Integer> curList : less){
				for(int usage : curList){
					curUsage-=usage;
				}
			}
			if(map.containsKey(cur.e)){
				map.get(cur.e).add(cur.u);
			}else{
				temp = new ArrayList<Integer>();
				temp.add(cur.u);
				map.put(cur.e,temp);
			}
			maxUsage = Math.max(curUsage,maxUsage);
		}
		
		return maxUsage;
	}
	
	public List<ArrayList<Integer>> getEndTimeLessThanCur(int cur,Map<Integer,ArrayList<Integer>> map){
		List<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		for(int end : map.keySet()){
			if(end < cur)
				result.add(map.get(end));
		}
		
		return result;
	}
	
	public static void main(String[] args){
		Log l1 = new Log(0,5,10);
		Log l2 = new Log(1,3,5);
		Log l3 = new Log(2,3,5);
		ArrayList<Log> ip = new ArrayList<Log>();
		ip.add(l1); ip.add(l2); ip.add(l3);
		LogMemory l = new LogMemory();
		System.out.println(l.calcMaxMemoryUsage(ip));
	}
	

}

class Log{
	int s,e,u;
	public Log(int start,int end, int usage){
		s=start; e= end; u = usage;
	}
	public String toString(){
		return String.valueOf(s) + ","+String.valueOf(e)+ "," + String.valueOf(u);
	}
}

public class LogMemory {
	
	public int calcMaxMemoryUsage(List<Log> ip){
		if(ip==null || ip.size()==0)
			return 0;
		if(ip.size() == 1)
			return ip.get(0).u;
		Collections.sort(ip, new Comparator<Log>(){
			public int compare(Log l1,Log l2){
				return l1.s-l2.s;
			}
		});
		
		Map<Integer,ArrayList<Integer>> map = new HashMap<>();
		ArrayList<Integer> temp = new ArrayList<Integer>();
		temp.add(ip.get(0).u);
		map.put(ip.get(0).e,temp);
		int curUsage = ip.get(0).u; int maxUsage = 0;
		for(int i=1;i<ip.size();i++){
			Log cur = ip.get(i);
			curUsage += cur.u;
			List<ArrayList<Integer>> less = getEndTimeLessThanCur(cur.s,map);
			for(List<Integer> curList : less){
				for(int usage : curList){
					curUsage-=usage;
				}
			}
			if(map.containsKey(cur.e)){
				map.get(cur.e).add(cur.u);
			}else{
				temp = new ArrayList<Integer>();
				temp.add(cur.u);
				map.put(cur.e,temp);
			}
			maxUsage = Math.max(curUsage,maxUsage);
		}
		
		return maxUsage;
	}
	
	public List<ArrayList<Integer>> getEndTimeLessThanCur(int cur,Map<Integer,ArrayList<Integer>> map){
		List<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
		for(int end : map.keySet()){
			if(end < cur)
				result.add(map.get(end));
		}
		
		return result;
	}
	
	public static void main(String[] args){
		Log l1 = new Log(0,5,10);
		Log l2 = new Log(1,3,5);
		Log l3 = new Log(2,3,5);
		ArrayList<Log> ip = new ArrayList<Log>();
		ip.add(l1); ip.add(l2); ip.add(l3);
		LogMemory l = new LogMemory();
		System.out.println(l.calcMaxMemoryUsage(ip));
	}
	

}

class Log{
	int s,e,u;
	public Log(int start,int end, int usage){
		s=start; e= end; u = usage;
	}
	public String toString(){
		return String.valueOf(s) + ","+String.valueOf(e)+ "," + String.valueOf(u);
	}
}

My Solution would be to create three classes,
MonthClass, DayClass, HoursClass,
in a hierarchical order.

We can instantiate an object for all the months, days and hours touched by the ranges provided in String input.

like:
[Root]
__l__
| |
[Jan] [Feb] ....
__|__ __|__
|
[Day1]....
|
[Hour1]...

And update the ranges for the hours.

Then a simple DFS can give us the Hour with the highest value!

P.S: Please feel free to slam on, if the sol. doent make sense.