Given a list of employee information like this:

[(3333, 1000, 2000), (1234, 1500, 3000), (999, 1700, 2100)]

Each item represents an employee. Those 3 numbers are the employee id,

the employee's start timestamp, and the employee's end timestamp.

We want to output a list of tuples containing a time range and the number

of employees who are working at the company.

[(1,1000,1500),(2,1500,1700),(3,1700,2000),(2,2000,2100),(1,2100,3000)]

Explanation: From time 1000 to 1500, only employee #3333 is working at the company,

so the number of employees is 1. From time 1500 to 1700, employee #3333 and #1234

are working for the company,so the number of employees is 2. Etc.

Solution 1: O(n log n + n^2); O(n)

  public static List<int[]> countEmployee(List<int[]> list) {
    Set<Integer> points = new TreeSet<>();
    for (int[] record : list) {
      points.add(record[1]);
      points.add(record[2]);
    }

    List<int[]> res = new ArrayList<>();
    List<Integer> temp = new ArrayList<>();
    for (int point : points) {
      temp.add(point);
    }

    for (int i = 0; i < temp.size() - 1; i++) {
      res.add(new int[]{0, temp.get(i), temp.get(i + 1)});
    }


    for (int[] r : res) {
      for (int[] record : list) {
        if (record[1] <= r[1] && record[2] >= r[2]) {
          r[0]++;
        }
      }
    }

    return res;
  }