aboutsummaryrefslogtreecommitdiff
path: root/max_length_pair_chain.c
blob: 606bf97bd555fa1bf96c89ce7570766470da364d (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
// 646. Maximum Length of Pair Chain
#include <stdio.h>
#include <stdlib.h>

/*
 * given a n array of 'n' pairs, where 'pairs[i]= [lefti, righti]' and 'left[i]
 * < right[i]'. a pair 'p2 = [c, d]' follows a pair 'p1 = [a, b]' if 'b < c'. a
 * chain of pairs can be formed in this fashion. return the length of the
 * longest chain which can be formed. you do not need to use up all the given
 * intervals. you can select pairs in any order.
 */

int cmp(int **a, int **b) {
  int *tmpa = *a;
  int *tmpb = *b;
  if (tmpa[1] == tmpb[1])
    return tmpa[0] - tmpb[0];
  return tmpa[1] - tmpb[1];
}

int findLongestChain(int **pairs, int pairs_size, int *pairs_col_size) {
  qsort(pairs, pairs_size, sizeof(int *), cmp);
  int ans = 1, k = 0;
  for (int i = 1; i < pairs_size; i++)
    if (pairs[i][0] > pairs[k][1]) {
      ans++;
      k = i;
    }
  return ans;
}

int main() {
  int p1[3][2] = {{1, 2}, {2, 3}, {3, 4}}, p2[3][2] = {{1, 2}, {7, 8}, {4, 5}};
  printf("%d\n", findLongestChain(p1, 3, NULL)); // expect: 2
  printf("%d\n", findLongestChain(p2, 3, NULL)); // expect: 3
}