CareerCup

Sort all the login times in one list, sort all the logout times in another list. This is O(NlogN) preprocessing. Now when a query comes along, do a binary search on both lists to count the number of logins and the number of logouts prior to the specified time. Then the number of logged in users is logins minus logouts. This query answering process is O(logN). So for N elements and D queries, we achieve O((N+D) log N) when we count both preprocessing and query cost.

segment tree

1) only query the number of users online once O(n): We can compare the each user's login time and logout time to the given time. If the login time is less than or equal to the given time and the logout time is greater than the given time, then then user is online.

2) Query m times the number of users online, where is m is large(O(mlogn + nlogn) instead of O(m*n)): we can precompute the number of users at certain times (times in the login and logout). Then we sort the times. Given a query time, we use binary search to find the largest time less than or equal to the given time and return the number of users online for this time.

import java.util.*;

public class UsersOnlineFinder {
    private List<Log> logs;
    //array size 2.
    //array[0]: # of login at this time
    //array[1]: # of logout at this time
    private Map<Integer, int[]> time_loginandout;
    private List<Integer> times;

    public UsersOnlineFinder(List<Log> logs) {
        this.logs = logs;
    }

    public int queryOnceMethod(int time) {
        int sum = 0;
	for(Log log : logs) {
	    int loginTime = log.getLoginTime();
	    int logoutTime = log.getLogoutTime();
	    if(loginTime <= time && time < logoutTime) {
	        sum++;
	    }
	}
	return sum;
    }

    public int preComputeMethod(int time) {
        int index = Collections.binarySearch(times,time);
	if(index < 0) {
	    index = -index - 1;
	    index--;
	}
	if(index < 0) {
	    return 0;
	}else {
	    int[] array = time_loginandout.get(times.get(index));
	    return array[0] - array[1];
	}
    }

    public void preCompute() {
        this.time_loginandout = new HashMap<Integer, int[]>();
	for(Log log : logs) {
	    updateLoginandout(log.getLoginTime(), 0);
	    updateLoginandout(log.getLogoutTime(), 1);
	}

        times = new ArrayList<Integer>(time_loginandout.keySet());
	Collections.sort(times);

	int sumLogin = 0;
	int sumLogout = 0;
	for(int time : times) {
	    int[] array = time_loginandout.get(time);
	    sumLogin += array[0];
	    array[0] = sumLogin;
	    sumLogout += array[1];
	    array[1] = sumLogout;
	}
    }

    //type 0 -- login, 1 -- logout
    public void updateLoginandout(int time, int type) {
	int[] array = time_loginandout.get(time);
	if(array == null) {
	    array = new int[2];
	    time_loginandout.put(time,array);
	}
	array[type]++;
    }

    public static void main(String[] args) {
        List<Log> logs = new ArrayList<Log>();
	logs.add(new Log(2, 10));
	logs.add(new Log(3, 7));
	logs.add(new Log(4, 10));
	logs.add(new Log(5, 8));
	logs.add(new Log(1, 8));
	UsersOnlineFinder finder = new UsersOnlineFinder(logs);
	System.out.println(finder.queryOnceMethod(0));
	System.out.println(finder.queryOnceMethod(6));
	System.out.println(finder.queryOnceMethod(8));
	System.out.println(finder.queryOnceMethod(10));
	System.out.println(finder.queryOnceMethod(11));
	System.out.println("--------------");
	finder.preCompute();
	System.out.println(finder.preComputeMethod(0));
	System.out.println(finder.preComputeMethod(6));
	System.out.println(finder.preComputeMethod(8));
	System.out.println(finder.preComputeMethod(10));
	System.out.println(finder.preComputeMethod(11));
    }
}

class Log {
    private int loginTime;
    private int logoutTime;

    public Log(int loginTime, int logoutTime) {
        this.loginTime = loginTime;
	this.logoutTime = logoutTime;
    }

    public int getLoginTime() {
        return loginTime;
    }

    public int getLogoutTime() {
        return logoutTime;
    }
}

segment tree is the best solution if there are huge number of users.

O(n)
Consider every login/logout pair, count it if login happened prior to the given time, and logout happened after the given time.

int users_logged_in(const vector<pair<int, int> >& logs, int curr_time) {
  int logged_in = 0;
  for (int i = 0; i < logs.size(); i++) {
    if (logs[i].first <= curr_time && logs[i].second > curr_time) 
      logged_in++;
  }
  return logged_in;
}

Interval tree is also fine