CareerCup

Use a treemap to keep a chronologically sorted set of events that map to the amount of RAM created or destroyed. Iterate over the keys to keep a running total of RAM used while keeping track of the highest amount.

public class HighestRAM {
	private static List<LogEntry> logEntries = new ArrayList<>();
	private static Map<Long, Long> times = new TreeMap<>();
	
	public static void main(String[] args) {
		logEntries.add(new LogEntry(0, 100, 500, 1));
		logEntries.add(new LogEntry(10, 70, 300, 2));
		logEntries.add(new LogEntry(50, 200, 1000, 3));
		logEntries.add(new LogEntry(110, 220, 400, 4));
		logEntries.add(new LogEntry(175, 280, 750, 5));
		
		System.out.println("Highest RAM used is: " + findHighRAM());
	}
	
	private static long findHighRAM() {
		long curRAM = 0, highRAM = 0;
		
		for (LogEntry entry : logEntries) {
			times.put(entry.startTime, entry.ram);
			times.put(entry.endTime, -1 * entry.ram);
		}
		
		for (Map.Entry<Long, Long> event : times.entrySet()) {
			curRAM += event.getValue();
			if (curRAM > highRAM) highRAM = curRAM;
		}
		
		return highRAM;
	}
	
	static class LogEntry {
		public final long startTime;
		public final long endTime;
		public final long ram;
		public final long jobId;
		
		public LogEntry(long sTime, long eTime, long ram, long id) {
			startTime = sTime;
			endTime = eTime;
			this.ram = ram;
			jobId = id;
		}
	}	
}

Sort the set of log entries by start time.
Remove the earliest start time from that set and add to a priority queue that orders by end time.
Compare the earliest time entry of the set from the queue, and add or remove and update the ram usage.
Finish when set is empty.

Running time: O(n lg(n))

This looks like interval problem. Using interval tree we should be able to find the intersecting or overlapping intervals. peakRAM would be maximum intersection in given input collection.

import java.util.*;

class logEntries{
	int startTime;
	int endTime;
	int RAMUsage;
	int id;
	logEntries(int startTime,int endTime, int RAMUsage,int id)
	{
		this.startTime=startTime;this.endTime=endTime;
		this.RAMUsage=RAMUsage;this.id=id;
	}
}
class entryNode
{
	int id;
	int time;
	int RAMUsage;
	entryNode(int id, int time, int RAMUsage)
	{
		this.id=id;
		this.time=time;
		this.RAMUsage=RAMUsage;
	}
}

public class peakRAM {
	
	public static Comparator<entryNode> entryComparator=new Comparator<entryNode>(){

		public int compare(entryNode n1, entryNode n2)
		{
			return (int)(Math.abs(n1.time)-Math.abs(n2.time));
		}
		
	};

	static int findPeakRam(ArrayList<logEntries> entries)
	{
		Queue<entryNode> entryPriorityQueue=new PriorityQueue<entryNode>(1,entryComparator);
		//Dividing the entries t
		for(logEntries en : entries)
		{
			entryPriorityQueue.add(new entryNode(en.id,en.startTime,en.RAMUsage));
			entryPriorityQueue.add(new entryNode(en.id,-en.endTime,en.RAMUsage));
		}
		//Polling the entries
		int Max=0,curr=0;
		while(true)
		{
			entryNode en=entryPriorityQueue.poll();

			if(en==null)
				break;
			//System.out.println("ID: "+en.id + " time : "+en.time + " RAMUsage : "+en.RAMUsage);
			if(en.time < 0)//
				curr-=en.RAMUsage;
			else 
			{
				curr+=en.RAMUsage;
				Max=Math.max(curr, Max);
			}
		}
		
		return Max;
	}
	public static void main(String[] args) {
		ArrayList<logEntries> entries=new ArrayList<logEntries>();
		entries.add(new logEntries(0, 100, 500, 1));
		entries.add(new logEntries(10, 70, 300, 2));
		entries.add(new logEntries(50, 200, 1000, 3));
		entries.add(new logEntries(110, 220, 400, 4));
		entries.add(new logEntries(175, 280, 750, 5));
		System.out.println(findPeakRam(entries));
		
	}

}

/*
public class LogEntry { 
public final long startTime; // start time of a job in millisec granularity 
public final long endTime; // end time of a job in millisec granularity. 
public final long ram; // the amount of ram the job occupies. 
public final long jobId; 
... constructor ... 
} 

running total of RAM 
| 
|             3GB 
|           ----- 
|      2GB 
|     ------ 
| 1GB                       ----------- 
|-----           ----------- 
| 
|____________________________________________________time 

Find the peakRAM when the input is a collection of LogEntry objects

for visual c++ 2005
*/

#include "stdafx.h"
#include <iostream>
#include <conio.h>
#include <algorithm>
#include <map>
#include <vector>
#include <list>
#include <iterator>
#include <math.h>
#include <numeric> 
#include <sstream>
#include <stack>
#include <string>

using namespace std;

struct LogEntry
{
	long startTime;
	long endTime;
	long ram;
	long jobId;

	LogEntry( long startTime_, long endTime_, long ram_,long jobId_)
	{
		startTime = startTime_;
		endTime = endTime_;
		ram = ram_;
		jobId = jobId_;
	}
};

struct MemEntry
{
	long nTime;
	long nMemAdd;

	MemEntry( long nTime_, long nMemAdd_ )
	{
		nTime = nTime_;
		nMemAdd = nMemAdd_;
	}
};

bool CompareFunc (MemEntry i,MemEntry j) 
{ 
	return (i.nTime < j.nTime); 
}

class Solution
{
public:
	static long CalcPeakMemory( vector<LogEntry> vecLogs )
	{
		vector<MemEntry> vecMem;
		for ( vector<LogEntry>::iterator it = vecLogs.begin(); it != vecLogs.end(); it ++ )
		{
			vecMem.push_back(MemEntry(it->startTime, it->ram));
			vecMem.push_back(MemEntry(it->endTime, -it->ram));
		}

		sort(vecMem.begin(), vecMem.end(), CompareFunc);

		long nResult = 0;
		long nResultTemp = 0;

		for ( vector<MemEntry>::iterator it2 = vecMem.begin(); it2 != vecMem.end(); it2 ++)
		{
			nResultTemp += it2->nMemAdd;
			nResult = max( nResult, nResultTemp );
		}

		return nResult;
	}
};


int _tmain(int argc, _TCHAR* argv[])
{
	vector<LogEntry> vecLogs;
	vecLogs.push_back(LogEntry( 0, 10, 15, 0));
	vecLogs.push_back(LogEntry( 0, 20, 30, 1));
	vecLogs.push_back(LogEntry( 15, 100, 50, 2));
	vecLogs.push_back(LogEntry( 50, 60, 20, 3));
	vecLogs.push_back(LogEntry( 100, 110, 5, 4));

	long nResult = Solution::CalcPeakMemory(vecLogs);

	cout << "The peakRAM is " << nResult << "." << endl;

	_getch();
	return 0;
}