1.3.3 Interval Partitioning

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

/*

Assigns intervals to the minimum number of groups so that no two intervals in the same group
overlap. This is the classic interval partitioning problem, also known as finding the minimum number
of rooms needed for meetings.

The greedy algorithm sorts intervals by start time and reuses the group whose current finish time is
earliest whenever possible. Otherwise, it creates a new group.

- `interval_partitioning(intervals)` returns a vector `room`, where `room[id]` is the assigned room
  for each input interval given as a vector of `PartitionInterval` with fields `start`, `finish`,
  and `id`. The number of rooms used in the returned assignment is $1 + \max(`room[id]`)$, or 0 if 
  there are no intervals.

Time Complexity:
- O(n log n) per call due to sorting and priority queue operations.

Space Complexity:
- O(n) auxiliary heap space.

*/

#include <algorithm>
#include <functional>
#include <queue>
#include <utility>
#include <vector>

struct PartitionInterval {
  int start, finish, id;
};

std::vector<int> interval_partitioning(std::vector<PartitionInterval> intervals) {
  std::sort(
      intervals.begin(), intervals.end(),
      [](const PartitionInterval &a, const PartitionInterval &b) {
        return a.start != b.start ? a.start < b.start : a.finish < b.finish;
      }
  );
  std::vector<int> room(intervals.size());
  std::priority_queue<
      std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>>
      pq;
  int rooms = 0;
  for (const auto &[start, finish, id] : intervals) {
    if (!pq.empty() && pq.top().first <= start) {
      int r = pq.top().second;
      pq.pop();
      room[id] = r;
    } else {
      room[id] = rooms++;
    }
    pq.emplace(finish, room[id]);
  }
  return room;
}

/*** Example Usage ***/

#include <algorithm>
#include <cassert>
using namespace std;

int main() {
  vector<PartitionInterval> intervals{{0, 30, 0}, {5, 10, 1}, {15, 20, 2}};
  vector<int> room = interval_partitioning(intervals);
  assert(1 + *max_element(room.begin(), room.end()) == 2);
  assert(room[1] == room[2]);
  assert(room[0] != room[1]);
  return 0;
}