aboutsummaryrefslogtreecommitdiff
path: root/my_calendar2.c
blob: b755fbcf854fe23b2c6b2d14f867325f67f90a15 (plain)
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
// 731. My Calendar II
#include "leetcode.h"

/*
 * you are implementing a program to use as your calendar. we can add a new
 * event if adding the event will not cause a triple booking. a triple booking
 * happens when three events have the same non empty intersection (ie. some
 * moment is common to all the three event). the event can be represented as a
 * pair of integers 'start' and 'end' that represents a booking on the half open
 * interval '[start, end]', the range of real numbers 'x' such that 'start <= x
 * < end'.
 */

struct interval {
  int start;
  int end;
};

typedef struct {
  struct interval *bookings;
  int bookings_size;
  struct interval *overlaps;
  int overlaps_size;
} MyCalendarTwo;

MyCalendarTwo *myCalendarTwoCreate() {
  MyCalendarTwo *obj = (MyCalendarTwo *)malloc(sizeof(MyCalendarTwo));
  obj->bookings = (struct interval *)malloc(1000 * sizeof(int));
  obj->bookings_size = 0;
  obj->overlaps = (struct interval *)malloc(1000 * sizeof(int));
  obj->overlaps_size = 0;
  return obj;
}

bool myCalendarTwoBook(MyCalendarTwo *obj, int start, int end) {
  for (int i = 0; i < obj->overlaps_size; i++)
    if (start < obj->overlaps[i].end && end > obj->overlaps[i].start)
      return false;
  for (int i = 0; i < obj->bookings_size; i++)
    if (start < obj->bookings[i].end && end > obj->bookings[i].start) {
      int overlap_start =
          start > obj->bookings[i].start ? start : obj->bookings[i].start;
      int overlap_end = end < obj->bookings[i].end ? end : obj->bookings[i].end;
      obj->overlaps[obj->overlaps_size++] =
          (struct interval){overlap_start, overlap_end};
    }
  obj->bookings[obj->bookings_size++] = (struct interval){start, end};
  return true;
}

void myCalendarTwoFree(MyCalendarTwo *obj) {
  free(obj->bookings);
  free(obj->overlaps);
  free(obj);
}

int main() {
  MyCalendarTwo *obj = myCalendarTwoCreate();
  printf("%d\n", myCalendarTwoBook(obj, 10, 20)); // expect: 1
  printf("%d\n", myCalendarTwoBook(obj, 50, 60)); // expect: 1
  printf("%d\n", myCalendarTwoBook(obj, 10, 40)); // expect: 1
  printf("%d\n", myCalendarTwoBook(obj, 5, 15));  // expect: 0
  printf("%d\n", myCalendarTwoBook(obj, 5, 10));  // expect: 1
  printf("%d\n", myCalendarTwoBook(obj, 25, 55)); // expect: 1
  myCalendarTwoFree(obj);
}